FWT算法总结

我们在学FFT的时候，计算的是这个式子

$$C_k=\sum_{i + j = k}A_iB_j$$

FWT是干啥的呢？它是算这个式子的

$$C_k=\sum_{i \oplus j = k}A_iB_j$$

其中那个$\oplus$代表3种双目逻辑运算中的任意一种$(or,and,xor)$，$A,B,C$代表向量（实在不懂就是个数组）

朴素算的话枚举$i,j$，是$O(n^2)$的。用和FFT差不多的思想，可以优化到$O(n \log n)$。其实实际过程也和FFT差不多，都是先把两个式子变换，直接相乘，再逆变换回去。。

首先定义向量的四则运算，其实还是蛮好猜的，就是按位计算。。加法就是按位加，乘法减法啥的都一样。

先以xor为例，设有两个向量$A,B$，它们的长度必须是$2^k$，要是不到就拿0补全。结果是$C$（也就是$C=A@B$，$@$表示这种卷积），显然$C$的长度也是$2^k$。xor的变换前人已经推出来的，具体怎么推实在是不用知道，因为就三种逻辑运算，这种东西也不需要推广啥的，这里只证明一下它的正确性。。

$k=0$时$$tf(A)=A$$
$k>0$时$$tf(A)=(tf(A_0)+tf(A_1),tf(A_0)-tf(A_1))$$

其中$A_0$表示一个向量，是$A_{0..2^{k-1}-1}$（就是向量$A$的前$2^{k−1}$维），$A_1$表示$A_{2^{k-1}..2^k-1}$，$(A_0,A_1)$表示把两段接起来。这就是一个分治的过程了

要证明它的正确性先要证个引理$tf(A+B)=tf(A)+tf(B)$

首先$k=0$时$tf(A+B)=A+B=tf(A)+tf(B)$
然后$k=1$时

$$tf(A+B)=(tf(A_0+B_0)+tf(A_1+B_1),tf(A_0+B_0)-tf(A_1+B_1))$$

我们设想一直往下拆，最后肯定会拆到$k=0$的情况，那就可以套用上面的（中间的过程就省去了）

$$tf(A+B)=(tf(A_0)+tf(B_0)+tf(A_1)+tf(B_1),tf(A_0)+tf(B_0)-tf(A_1)+tf(B_1))$$

可以设想一下，先加再接起来和先接起来再加其实是一样的，因为都是按位加，所以就可以移下项

$$tf(A+B)=(tf(A_0)+tf(A_1),tf(A_0)−tf(A_1))+(tf(B_0)+tf(B_1),tf(B_0)−tf(B_1))$$

这就是上面的定义

$$tf(A+B)=tf(A)+tf(B)$$

这样就证明了这个引理。

接下来就是证明转换后的向量直接乘法就可以推出卷积后的向量（和FFT的思想一样）：$tf(C)=tf(A)\times tf(B)$

首先$k=0$时，$tf(C)=C=A\times B=tf(A)\times tf(B)$
对于$k>0$，也是归纳法

$$tf(A)\times tf(B)=(tf(A_0)+tf(A_1),tf(A_0)−tf(A_1))\times (tf(B_0)+tf(B_1),tf(B_0)−tf(B_1))$$

移下项

$$=((tf(A_0)+tf(A_1))\times (tf(B_0)+tf(B_1)),(tf(A_0)-tf(A_1))\times (tf(B_0)-tf(B_1))$$

拆开括号

$$=(tf(A_0)\times tf(B_0)+tf(A_0)\times tf(B_1)+tf(A_1)\times tf(B_0)+tf(A_1)\times tf(B_1),tf(A_0)\times tf(B_0)-tf(A_0)\times tf(B_1)-tf(A_1)\times tf(B_0)+tf(A_1)\times tf(B_1))$$

这就又变成了一个分治的过程，又可以一直拆到$k=0$的时候，这样所有的乘法都可以化成卷积的形式

$$=(tf(A_0@B_0)+tf(A_0@B_1)+tf(A_1@B_0)+tf(A_1@B_1),tf(A_0@B_0)-tf(A_0@B_1)-tf(A_1@B_0)+tf(A_1@B_1))$$

我们先记住这个式子，先来研究一下$C$，$C=(C_0,C_1)$，我们发现这两个的区别就是最高位是0还是1，而且我们还根据最高位是0还是1，把A和B都拆成了两部分。所以

$$C=(C_0,C_1)=(A_0@B_0+A_1@B_1,A_0@B_1+A_1@B_0)$$

这里$C_0=A_0@B_0+A_1@B_1$表示着当A的最高位为0且B的最高位是0时，或者当A的最高位为1且B的最高位是1时，xor出来的结果最高位是0。后面的同理。

这样就可以化式子了

$$tf(C)=(tf(C_0)+tf(C_1),tf(C_0)-tf(C_1))$$

带入上面的结论

$$=(tf(A_0@B_0+A_1@B_1)+tf(A_0@B_1+A_1@B_0),tf(A_0@B_0+A_1@B_1)-tf(A_0@B_1+A_1@B_0))$$

用引理拆开

$$=(tf(A_0@B_0)+tf(A_1@B_1)+tf(A_0@B_1)+tf(A_1@B_0),tf(A_0@B_0)+tf(A_1@B_1)-tf(A_0@B_1)+tf(A_1@B_0))$$

这就等于上面的那个式子了，所以$tf(C)=tf(A)\times tf(B)$。

正着这就这么证完了，逆运算呢？

$$uft(ft(A))=uft(tf(A_0+A_1),tf(A_0-A_1))$$

$$=uft(ft(A_0)+ft(A_1),ft(A_0)-ft(A_1))$$

那么就令$uft(A)=(uft({A_0+A_1 \over 2}),uft({A_0-A_1 \over 2}))$

则

$$uft(ft(A))=(uft(ft(A_0)),uft(ft(A_1)))=(A_0,A_1)=A$$

剩下的两种也是一样的推，就是对于$C$研究的时候有些不一样，就不往上写了，三种结论是这样的：

xor
$$tf(A)=(tf(A_0)+tf(A_1),tf(A_0)-tf(A_1))$$

$$uft(A)=(uft({A_0+A_1 \over 2}),uft({A_0-A_1 \over 2}))$$

or
$$tf(A)=(tf(A_0),tf(A_1)+tf(A_0))$$

$$utf(A)=(uft(A_0),uft(A_1)-uft(A_0))$$

and
$$tf(A)=(tf(A_0)+tf(A_1),tf(A_1))$$

$$utf(A)=(utf(A_0)-uft(A_1),utf(A_1))$$

最后就是关于实现的方式。虽然是个递归式，但我们肯定不会递归着写它。观察每层递归都会把序列分成$2^p$长度的几份，再在里面计算，我们可以从底往上得总结答案，区间长度从$1$到$2^k$，代码如下

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;
                //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;
                //rev表示2在模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)  //n=2^k
{
    FWT(a,n);
    FWT(b,n);
    for(int i=0;i<n;i++) a[i]=1ll*a[i]*b[i]%mod;
    UFWT(a,n);
}

其中第一层循环乘第二次循环是$O(n)$的，第二层是$O(\log n)$的，总复杂度$O(n \log n)$的。