后面的图片将会告诉:
如何推出FWT的公式tf
如何推出FWT的逆公式utf
用的是设系数,求系数的方法!
=========================================================
以一种高度思考
http://picks.logdown.com/posts/179290-fast-walsh-hadamard-transform
加和乘的定义
大小为1时的公式
https://blog.csdn.net/zhshrs/article/details/54838466
证明
https://blog.csdn.net/john123741/article/details/76576925
写成
or
tf(A)=(tf(A0),tf(A1)+tf(A0))
utf(A)=(utf(A0),utf(A1)-utf(A0))
and
tf(A)=(tf(A0)+tf(A1),tf(A1))
utf(A)=(utf(A0)-utf(A1),utf(A1))
xor
tf(A)=(tf(A0)+tf(A1),tf(A0)-tf(A1))
utf(A)=(1/2*(utf(A0)+utf(A1)),1/2*(utf(A0)-utf(A1)))
更好记忆一点
对于or,and
0 = 0 or 0 对应 or tf(A0)[utf(A0)]
1 = 1 and 1 对应 and tf(A1)[utf(A1)]
=================================
and or xor 二进制操作
0~2^(k-1)-1时,最高位为0
2^(k-1)~2^k-1时,最高位为1
e.g.
000
001
010
011
----
100
101
110
111
P.S.:
FFT和FWT,两者虽然实现方法都是内容分半(二分),但是其本质原理不同。
FFT: http://www.cnblogs.com/zwfymqz/p/8244902.html
快速莫比乌斯变换
study from :
https://yhx-12243.github.io/OI-transit/records/vijos%20%234.html
适用于and or,xor 行不通
FMT写法和FWT是一样的,两者考虑问题角度不一样。
https://www.luogu.org/problemnew/show/P4717
存储函数地址
void (*addr1[3])(ll a[])={fwt1,fwt2,fwt3};
void (*addr2[3])(ll a[])={ufwt1,ufwt2,ufwt3};
also can use (int type)=1ll*...
注意当数字范围为[0,x]
遍历范围 [0,z) tot=2*x(大于any i op j, 其中i,j in [0,x])
而数组开z大小
对于代码中的tot,要写成2^k的形式,
否则如写成tot,e.g. tot=9, 8(i)+3(j)>9。
对应好记忆
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long const double eps=1e-;
const ll inf=1e9;
const ll mod=;
const int maxn=(<<)*; ///any n or <2n /**
补全为2^k
**/ ll aa[maxn],bb[maxn],a[maxn],b[maxn];
int tot;
ll mod_inv_2=(mod+)/; ///or
void fwt1(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=,cnt_cur=;cnt_pre<tot;cnt_pre<<=,cnt_cur<<=)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j+cnt_pre]+=a[i+j])%=mod;
} void ufwt1(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=tot>>,cnt_cur=tot;cnt_pre>;cnt_pre>>=,cnt_cur>>=)
// for (cnt_pre=1,cnt_cur=2;cnt_pre<tot;cnt_pre<<=1,cnt_cur<<=1)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j+cnt_pre]-=a[i+j]-mod)%=mod;
} ///and
void fwt2(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=,cnt_cur=;cnt_pre<tot;cnt_pre<<=,cnt_cur<<=)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j]+=a[i+j+cnt_pre])%=mod;
} void ufwt2(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=tot>>,cnt_cur=tot;cnt_pre>;cnt_pre>>=,cnt_cur>>=)
// for (cnt_pre=1,cnt_cur=2;cnt_pre<tot;cnt_pre<<=1,cnt_cur<<=1)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j]-=a[i+j+cnt_pre]-mod)%=mod;
} ///xor
void fwt3(ll *a)
{
int cnt_pre,cnt_cur,i,j;
ll x;
for (cnt_pre=,cnt_cur=;cnt_pre<tot;cnt_pre<<=,cnt_cur<<=)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
{
x=a[i+j];
a[i+j]=(a[i+j]+a[i+j+cnt_pre])%mod;
a[i+j+cnt_pre]=(x-a[i+j+cnt_pre]+mod)%mod;
}
} void ufwt3(ll *a)
{
int cnt_pre,cnt_cur,i,j;
ll x;
for (cnt_pre=tot>>,cnt_cur=tot;cnt_pre>;cnt_pre>>=,cnt_cur>>=)
// for (cnt_pre=1,cnt_cur=2;cnt_pre<tot;cnt_pre<<=1,cnt_cur<<=1)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
{
x=a[i+j];
a[i+j]=(a[i+j]+a[i+j+cnt_pre])*mod_inv_2%mod;
a[i+j+cnt_pre]=(x-a[i+j+cnt_pre]+mod)*mod_inv_2%mod; ///x-
}
} int main()
{
int n,i,j;
scanf("%d",&n);
tot=<<n;
for (i=;i<tot;i++)
scanf("%lld",&aa[i]);
for (i=;i<tot;i++)
scanf("%lld",&bb[i]); void (*addr1[]) (ll a[])={fwt1,fwt2,fwt3};
void (*addr2[]) (ll a[])={ufwt1,ufwt2,ufwt3}; for (i=;i<;i++)
{
memcpy(a,aa,sizeof(aa));
memcpy(b,bb,sizeof(bb));
(*addr1[i])(a);
(*addr1[i])(b);
for (j=;j<tot;j++)
a[j]=a[j]*b[j]%mod;
(*addr2[i])(a);
for (j=;j<tot;j++)
printf("%lld%c",a[j],j==tot-?'\n':' ');
}
return ;
}
/*
0
1000000
1000000 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
*/
对应下方的图片公式推导
tf a0+a1 a1-a0
utf a1 a0
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long const double eps=1e-;
const ll inf=1e9;
const ll mod=;
const int maxn=(<<)*; ///any n or <2n /**
补全为2^k
**/ ll aa[maxn],bb[maxn],a[maxn],b[maxn];
int tot;
ll mod_inv_2=(mod+)/; ///or
void fwt1(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=,cnt_cur=;cnt_pre<tot;cnt_pre<<=,cnt_cur<<=)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j+cnt_pre]+=a[i+j])%=mod;
} void ufwt1(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=tot>>,cnt_cur=tot;cnt_pre>;cnt_pre>>=,cnt_cur>>=)
// for (cnt_pre=1,cnt_cur=2;cnt_pre<tot;cnt_pre<<=1,cnt_cur<<=1)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j+cnt_pre]-=a[i+j]-mod)%=mod;
} ///and
void fwt2(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=,cnt_cur=;cnt_pre<tot;cnt_pre<<=,cnt_cur<<=)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j]+=a[i+j+cnt_pre])%=mod;
} void ufwt2(ll *a)
{
int cnt_pre,cnt_cur,i,j;
for (cnt_pre=tot>>,cnt_cur=tot;cnt_pre>;cnt_pre>>=,cnt_cur>>=)
// for (cnt_pre=1,cnt_cur=2;cnt_pre<tot;cnt_pre<<=1,cnt_cur<<=1)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
(a[i+j]-=a[i+j+cnt_pre]-mod)%=mod;
} ///xor
void fwt3(ll *a)
{
int cnt_pre,cnt_cur,i,j;
ll x;
for (cnt_pre=,cnt_cur=;cnt_pre<tot;cnt_pre<<=,cnt_cur<<=)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
{
x=a[i+j];
(a[i+j]+=a[i+j+cnt_pre])%=mod;
(a[i+j+cnt_pre]-=x-mod)%=mod; ///-x
}
} void ufwt3(ll *a)
{
int cnt_pre,cnt_cur,i,j;
ll x;
for (cnt_pre=tot>>,cnt_cur=tot;cnt_pre>;cnt_pre>>=,cnt_cur>>=)
// for (cnt_pre=1,cnt_cur=2;cnt_pre<tot;cnt_pre<<=1,cnt_cur<<=1)
for (i=;i<tot;i+=cnt_cur)
for (j=;j<cnt_pre;j++)
{
x=a[i+j];
a[i+j]=(a[i+j]+a[i+j+cnt_pre])*mod_inv_2%mod;
a[i+j+cnt_pre]=(x-a[i+j+cnt_pre]+mod)*mod_inv_2%mod; ///x-
}
} int main()
{
int n,i,j;
scanf("%d",&n);
tot=<<n;
for (i=;i<tot;i++)
scanf("%lld",&aa[i]);
for (i=;i<tot;i++)
scanf("%lld",&bb[i]); void (*addr1[]) (ll a[])={fwt1,fwt2,fwt3};
void (*addr2[]) (ll a[])={ufwt1,ufwt2,ufwt3}; for (i=;i<;i++)
{
memcpy(a,aa,sizeof(aa));
memcpy(b,bb,sizeof(bb));
(*addr1[i])(a);
(*addr1[i])(b);
for (j=;j<tot;j++)
a[j]=a[j]*b[j]%mod;
(*addr2[i])(a);
for (j=;j<tot;j++)
printf("%lld%c",a[j],j==tot-?'\n':' ');
}
return ;
}
/*
0
1000000
1000000 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
*/
and,or,xor等操作
C=A@B @为卷积运算(通过两个函数生成第三个函数的一种数学算子)
目标:tf(C)=tf(A)*tf(B)
设置tf(X)=(... , ...) 使满足上述条件
基础部分
公式推导
验证公式正确性