FWT

转载自https://blog.csdn.net/liangzhaoyang1/article/details/52819835

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

其中指任一二元逻辑位运算。

一些基础的想法：
为了加速这个运算，我们还是需要用一些类似FFT的东西。
注意到位运算都是有位独立性的，那么每次我们只考虑某一位？
不妨假设：

那么，我们的目标就是求出：

假如构造了一个变换 ，满足：

且可以在较短时间内进行变换及其逆变换，那么我们的目标就可以实现了。
似乎便不能继续往下走了，那我们具体情况具体分析。

XOR

当指异或运算的时候，即 SRM518 Nim 那题中所需要的方法。
此时：

接下来怎么来找变换 ？其实我并不知道这个变换是怎么找到的（可能哪个无聊的正好构造出来了？或者从很小的情况中顺藤摸瓜出来了？）。
但是这个变换确实存在，且形式比较漂亮。

虽然不知道这个是怎么构造出来的，不过我们还是可以很轻易地验证的。

AND

当指与运算的时候，也是可以做的。
变换为：

同样轻易可验证。

OR

当指或运算的时候，可以类比于与运算的变换：

XNOR,NAND,NOR

当指异或非运算、与非运算、或非运算时。
我们可以将 直接用异或运算、与运算、或运算的方法求出来，然后将互反的两位交换即可。

代码：
这里只贴一个与运算的代码，别的运算都可以类似实现。

void FWT( ll X[], int l, int r, int v ) {
if ( l == r ) return;
int m = ( l + r ) >> 1;
FWT( X, l, m, v ); FWT( X, m + 1, r, v );
FOR ( i, 0, m - l ) {
X[ l + i ] += X[ m + 1 + i ] * v;
}
}

模板：

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)
{
FWT(a,n);
FWT(b,n);
for(int i=0;i<n;i++) a[i]=1LLa[i]*b[i]%mod;
UFWT(a,n);
}