快速沃尔什变换（FWT）讲解 解决集合卷积的方法

能看到这篇博客的人，一定知道FWT是干什么的。（什么？你不知道？）
没事，这里有pick讲FWT的博客。先点进去看一看。
如果你看懂了，那么恭喜你。如果你跟我一样看不懂，那么请继续往下看。

这里的A和B都是什么呢？其实它们是一个多维的向量（如果你不知道向量是什么，就把它当成数组），下标从0开始。
其中，$A = <a_{0},a_{1},...,a_{2^{k}-1}>$，$B = <b_{0},b_{1},...,b_{2^{k}-1}>$，$C = A\otimes B$
这里我们定义 $$A\pm B = < a_{0}\pm b_{0}, a_{1}\pm b_{1},..., (a_{2^{k}-1})\pm (b_{2^{k}-1}) >$$ 即对应位相加（减） $$A * B = < a_{0} * b_{0}, a_{1} * b_{1},..., (a_{2^{k}-1}) * (b_{2^{k}-1}) >$$ 即对应位相乘$A\otimes B$ 为A和B做卷积之后得到的结果，也是一个和原来大小一样的向量。

注意到FWT做的是二进制上的位运算，所以一定要把A和B补到2的整次幂次（即不足的地方填上0）。

我们要构造一个变换tf，使得$tf(A)*tf(B)=tf(C)$。这个变换的对象是一个大小为$2^{k}$的向量，变换出来的结果也是一个大小为$2^{k}$的向量。

就以异或举例。picks告诉我们 $$tf(A)=(tf(A_{0})+tf(A_{1}),tf(A_{0})-tf(A_{1}))$$ $$A_{0}=<a_{0},a_{1},...,a_{2^{k-1}-1}>$$ $$A_{1}=<a_{2^{k-1}},a_{2^{k-1}+1},...,a_{2^{k}-1}>$$ 即把A中的下标按照二进制最高位为0或1分成前后两部分（前面的为$A_{0}$,后面的为$A_{1}$），分治下去做。

分治之后得到$tf(A_{0})$和$tf(A_{1})$。然后tf$A$的前半部分$即$[0,2^{k-1}-1]$$为$tf(A_{0})+tf(A_{1})$，后半部分（即$[2^{k-1},2^{k}-1]$）为$tf(A_{0})-tf(A_{1})$。（其实就是已知两个向量，把两个向量做加减运算，加的那个结果填到前一半中，减的那个结果填到后一半中）。

然而，这为什么是对的？
接下来我们来证明它是对的。

我要事先说明（注意不是证明）一个引理:$tf(A+B)=tf(A)+tf(B)$。这个东西看上去挺直观的（一点都不直观好吗。。）。这个东西可以用数学归纳法证。这里略过。。。（有时间的时候再补上）

我们看k=1的时候。根据定义，有 $$tf(A)=<a_{0}+a_{1},a_{0}-a_{1}>$$ $$tf(B)=<b_{0}+b_{1},b_{0}-b_{1}>$$ $$tf(C)=<c_{0}+c_{1},c_{0}-c_{1}>$$ $$c_{0}=a_{0}*b_{0}+a_{1}*b_{1},c_{1}=a_{0}*b_{1}+a_{1}*b_{0}$$ 自己代代看，反正代出来很神奇的的发现$tf(A)*tf(B)=tf(C)$

接下来使用数学归纳法。假设对于大小都为$2^{k}(k\epsilon N)$的向量A和B，满足$C = A\otimes B$，并且$tf(A)*tf(B)=tf(C)$。
考虑当大小为$2^{k+1}$的情况。我们要证明在这种情况下，$tf(A)*tf(B)=tf(C)$。根据定义，有
$$tf(A)=(tf(A_{0})+tf(A_{1}),tf(A_{0})-tf(A_{1}))$$ $$tf(B)=(tf(B_{0})+tf(B_{1}),tf(B_{0})-tf(B_{1}))$$ $$tf(A)*tf(B)=([tf(A_{0})+tf(A_{1})]*[tf(B_{0})+tf(B_{1})],[tf(A_{0})-tf(A_{1})]*[tf(B_{0})-tf(B_{1})])$$
暴力把式子拆开，有
$tf(A)*tf(B)=$
$$(tf(A_{0})*tf(B_{0})+tf(A_{0})*tf(B_{1})+tf(A_{1})*tf(B_{0})+tf(A_{1})*tf(B_{1}),$$ $$tf(A_{0})*tf(B_{0})+tf(A_{1})*tf(B_{1})-tf(A_{0})*tf(B_{1})-tf(A_{1})*tf(B_{0}))$$
注意到这里的$A_{0}$,$A_{1}$,$B_{0}$,$B_{1}$都是大小为$2^{k}$的向量，符合归纳的基础。于是，
$tf(A)*tf(B)=$
$$(tf(A_{0}\otimes B_{0})+tf(A_{0}\otimes B_{1})+tf(A_{1}\otimes B_{0})+tf(A_{1}\otimes B_{1}),$$ $$tf(A_{0}\otimes B_{0})+tf(A_{1}\otimes B_{1})-tf(A_{0}\otimes B_{1})-tf(A_{1}\otimes B_{0}))$$
由于异或每一位是独立，而这里如果我们把C按照最高位为0或1分成两部分，最高位的异或和其它位不相关。
于是有 $$C=(C_{0},C_{1})=(A_{0}\otimes B_{0}+A_{1}\otimes B_{1},A_{0}\otimes B_{1}+A_{1}\otimes B_{0})$$
要证的等式
$$右边=tf(C)=tf(C_{0},C_{1})$$ $$=tf(A_{0}\otimes B_{0}+A_{1}\otimes B_{1},A_{0}\otimes B_{1}+A_{1}\otimes B_{0})$$ $$=(tf(A_{0}\otimes B_{0}+A_{1}\otimes B_{1})+tf(A_{0}\otimes B_{1}+A_{1}\otimes B_{0}),tf(A_{0}\otimes B_{0}+A_{1}\otimes B_{1})-tf(A_{0}\otimes B_{1}+A_{1}\otimes B_{0}))$$ $$=(tf(A_{0}\otimes B_{0})+tf(A_{1}\otimes B_{1})+tf(A_{0}\otimes B_{1})+tf(A_{1}\otimes B_{0}),tf(A_{0}\otimes B_{0})+tf(A_{1}\otimes B_{1})-tf(A_{0}\otimes B_{1})-tf(A_{1}\otimes B_{0}))$$ $$=tf(A)*tf(B)=左边$$
至此，证毕。

然而这只是一个tf，还有一个逆变换utf。这个逆变换的正确性可以用同样的方法证明，即先看k=1的情况，然后一步一步用数归推上去。
证明方法比较简单（真的很简单），这里略过。

至于其它位运算，其证明方法与异或一致，这里不赘述。

说了这么多，其实这个证明并没有什么卵用（只是使得自己相信它是对的）。。大家还是背代码吧。。。

看完的找个模板题练练手感受一下吧，CSU 1911 Card Game

模板：

// 题目要求取模时使用mod，否则去除mod
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];
                int 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];
                int 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] = 1LL * a[i] * b[i] % mod;
    }
    UFWT(a, n);
}