FWT快速沃尔什变换

Fast Walsh-Hadamard Transform 就是用于解决一类卷积问题的方法。

时间复杂度nlogn，求解的内容如下

可以用于求解数组A和数组B异或后能得到哪些数之类的问题(暴力枚举是n²的复杂度)

void FWT(int a[],int n)
{
for(int d=1;d<n;d<<=1)
for(int m=d<<1,i=0;i<n;i+=m)
for(int j=0;j<d;j++)
{
int x=a[i+j],y=a[i+j+d];
//a[i+j]=(x+y)%mod,a[i+j+d]=(x-y+mod)%mod;

//xor:
a[i+j]=x+y,a[i+j+d]=(x-y+mod)%mod;
//and:a[i+j]=x+y;

//or:a[i+j+d]=x+y;

}
}
void UFWT(int a[],int n)
{
for(int d=1;d<n;d<<=1){
for(int m=d<<1,i=0;i<n;i+=m) {
for(int j=0;j<d;j++)
{
int x=a[i+j],y=a[i+j+d];
//a[i+j]=1LL*(x+y)*rev%mod,a[i+j+d]=(1LL*(x-y)*rev%mod+mod)%mod;
//xor:
a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2;
//and:a[i+j]=x-y;

//or:a[i+j+d]=y-x;

}
}
}
}
void solve(int a[],int b[],int n)
{
//求解C[i]=segma(j^k==i?a[j]*b[k]:0),时间复杂度nlogn 
//可用于求解n个数两两异或能得到哪些数,c[i]!=0表示该数能求解得到。
FWT(a,n);
FWT(b,n);
for(int i=0;i<n;i++) a[i]=1LL*a[i]*b[i]%mod;
UFWT(a,n);
}

最后

以上就是酷炫月饼为你收集整理的FWT快速沃尔什变换的全部内容，希望文章能够帮你解决FWT快速沃尔什变换所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。