真正理解快速沃尔什变换/快速莫比乌斯变换(FWT|FMT) (已完结)

## 1、快速莫比乌斯变换
###1.1 什么是莫比乌斯变换
　　　快速莫比乌斯变换，简称(FMT)，也是一种对数列的变换。类似FFT地，FMT也是通过将数列/多项式在两种形式下来回变换达到加速两个数列/多项式卷积的效果。
　　　FFT解决的是这样的卷积：
　　　$$C_x=\sum_{i+j=x}a_ib_j$$
　　　其中$x,i,j$是整数。
　　　不会FFT的读者也不用担心，FMT比FFT好懂很多。只是会了FFT可以比较轻松地理解FMT做的事情。
　　　而FMT解决的是这样的卷积：
　　　$$C_x=\sum_{i\cup j=x}a_ib_{j}$$
　　　其中$x,i,j$是集合。可以用二进制整数表示。

###1.2 如何完成莫比乌斯变换
　　　加速卷积的最常见方法是化卷积为乘积。
　　　我们考虑把两个数列做一种特定的变换。
　　　定义$A$的莫比乌斯变换$FMT(A)$
　　　定义$X_i$为$X$的第$i$项。
　　　我们要求:
　　　$$\sum_{i\cup j=x}A_iB_{j}=C_x$$
　　　如果$FMT$满足：
　　　$$FMT(A)_i*FMT(B)_i=FMT(C)_i$$
　　　那么就好了。
　　　我们发现我们可以很轻易地构造出$FMT$。
　　　定义：$$FMT(A)_n=\sum_{i\subseteq n}A_i$$
　　　更直白地说，也就是对$A$做子集和。
　　　考虑为什么可以这样构造
　　　首先$FMT(A),FMT(B)$的每一项$x$都表示了原数列中的子集和。因此$FMT(A)*FMT(B)$用乘法分配律展开包含了$C$所有子集的贡献，也就是：
　　　$$\sum_{i\subseteq x}A_i\sum_{j\subseteq x}B_j=\sum_{i,j\subseteq x}A_iB_j=\sum_{k\subseteq x}\sum_{i\cup j=k}A_iB_j$$
　　　考虑到：$$\sum_{i\cup j=x}A_iB_{j}=C_x$$
　　　诶，那不是就做完了？
　　　有$$FMT(A)_x*FMT(B)_x=\sum_{k\subseteq x} C_k=FMT(C)_x$$
　　　实际上就是利用集合并卷积的特殊性，做了个子集前缀和优化了一下……
　　　是不是很简单。

### 1.3 快速莫比乌斯变换
　　　现在我们只要快速的完成子集和操作，那么我们就可以快速的完成莫比乌斯变换的过程了。
　　　我们考虑一种增量构造的分治算法。
　　　首先我们将集合中的元素依次编号为$1-n$，方便二进制表示。
　　　第$i$层我们先把集合按照后$n-i$个元素的状态分类，这样在每一类中我们只需要处理**后$n-i$个元素相同**的集合。
　　　然后我们考虑由$i$层转移到$i+1$层，发现只是多了一个元素的状态。讨论一下这个元素取不取，发现这个元素不取，答案就和原来一样，因为它的子集和不变。如果这个元素要取，那么这个元素不取是它的子集，会多出这个元素不取的子集和。最终我们发现，到第$i$层只需要把第$i$个元素不取的状态加到第$i$个元素取的状态就可以了。用图来表示，一种颜色代表一层，一个箭头代表累加，竖线代表每层的分类，集合用二进制表示从右到左是低位到高位：
　　　![一个栗子](https://leanote.com/api/file/getImage?fileId=5bf20918ab64411b7b0012e2)
　　　代码就很简单了：
```
void FMT(int * A, int n, int t) {
    for(int i = 1; i < (1 << n); i <<= 1)
        for(int p = i << 1, j = 0; j < (1 << n); j += p)
            for(int k = 0; k < i; ++k)
                A[i + j + k] += A[j + k];
}
```
　　　那么要变回去怎么办呢？
　　　提醒自己，只要把贡献扣回来就行了。
　　　所以我们用一样的思想，只是把累加改成扣除。
```
void FMT(int * A, int n, int t) {
    for(int i = 1; i < (1 << n); i <<= 1)
        for(int p = i << 1, j = 0; j < (1 << n); j += p)
            for(int k = 0; k < i; ++k)
                A[i + j + k] -= A[j + k];
}
```
　　　一般都是要取模的，带上模数就好。

## 2、快速沃尔什变换
###2.1 如何完成沃尔什-阿达玛变换
　　　快速沃尔什变换(Fast Walsh-Hadamard Transform，全称快速沃尔什-阿达玛变换)的过程就比FMT要稍微复杂一些了，但是通过深入了解(FWT)的过程，我们将进一步了解线性变换的本质。
　　　考虑模仿莫比乌斯变换，我们将卷积变为乘积形式。
　　　定义若
　　　$$C_x=\sum_{i \bigoplus j=x}A_iB_j$$
　　　其中$\bigoplus$为集合异或操作，也可以看成二进制不进位加法。
　　　那么我们令$FWT(F)$满足
　　　$$FWT(C)_x=FWT(A)_xFWT(B)_x$$
　　　
　　　考虑到$FWT(F)$的结果的每一项一定是和原来的$F$线性相关的(不会有原来的项相乘的关系，因为我们做的变换使用加减法)。那么究竟如何相关的呢？
　　　我们设对$n$项的数列$F$的变换为
　　　$$FWT(F)_x=\sum^{n}_{i=0} g(x,i)F_i$$
　　　因为线性相关，我们定义$g(x,i)$为系数
　　　那么我们的目标就是：
　　　$$\sum^{n}_{i=0} g(x,i)C_i = \sum^{n}_{j=0} g(x,j)A_j \sum^{n}_{k=0} g(x,k)B_k$$
　　　用$C_x=\sum_{i \bigoplus j=x}A_iB_j$代入
　　　$$\sum^{n}_{i=0} g(x,i)\sum_{j \bigoplus k=i}A_jB_k = \sum^{n}_{j=0} g(x,j)A_j \sum^{n}_{k=0} g(x,k)B_k$$
　　　化简可得
　　　$$\sum^{n}_{j=0}\sum^{n}_{k=0} g(x, {j \bigoplus k})A_jB_k = \sum^{n}_{j=0}\sum^{n}_{k=0} g(x,j)g(x,k)A_j  B_k$$
　　　现在就很明了了，我们只需要使得：
　　　$$g(x,j)g(x,k)=g(x,{j \bigoplus k})$$
　　　考虑异或之后$i,j$的什么属性会变成$i,j$属性的乘积
　　　不难发现，这里有一个小结论：
　　　对于异或操作来说，异或前后$1$的个数的奇偶性不会改变，也就是说$i,j$中$1$的个数加起来和$i\bigoplus j$中$1$的个数的奇偶性是一样的。
　　　考虑$i \bigoplus j$的过程的每一位
　　　1、如果这一位不同，那么$1$的个数不会发生改变
　　　2、如果这一位相同，全是$0$时$1$的个数不会改变，全是$1$时$1$的个数减去$2$，同样不改变奇偶性。
　　　利用这一性质，我们定义
　　　$$g(x,i)=(-1)^{|i\cap x|}$$
　　　和FMT一样，每一项其实是二进制表示的集合，因此使用集合交符号$"\cap" $与集合大小符号$"|S|"$。
　　　注意到$i\cap x$实际上可以看作是在$i$中取$x$中是$1$的位出来，显然可以知道$(i\cap x)\bigoplus (j\cap x)=(i\bigoplus j)\cap x$。也就是异或对交有分配律。
　　　容易证明$g$满足：
　　　$$g(x,j)g(x,k)=g(x,{j \bigoplus k})$$
　　　那么现在就很清晰了，我们翘首以盼的$FWT$的真面目终于浮出了水面：
　　　$$FWT(F)_x=\sum^{n}_{i=0}(-1)^{|i\cap x|}F_i$$
　　　也就是每一个位置对于$FWT(F)_x$都有贡献，贡献正负由交集大小的奇偶性确定。
　　　
###2.2 快速沃尔什-阿达玛变换
　　　考虑模仿$FMT$位分治逐位满足的思想来完成这个变换：
　　　每一次考虑新加入第$i$个物品取不取的情况，将当前集合分为$i$取和$i$不取，$i$取的放右边，$i$不取的放左边。$i$取的话，和$i$取的状态取并后集合大小不变，和$i$不取的状态取并后集合大小$-1$。$i$不取的话，和$i$取的状态取并后集合大小不变，和$i$不取的状态取并后集合大小同样的不变。
　　　这样考虑原有状态，左右两边对$i$不取的贡献都是$+$，因为集合大小不变。左边对$i$取的贡献是$+$，右边对$i$取的贡献是$-$，因为都取$i$的话并集增加了$1$，贡献取反。
　　　这样我们每一次令：
　　　$$A[j + k] = A[j + k] + A[j + i + k] \\A[j + i + k] = A[j + k] - A[j + i + k]$$
　　　就完成了正变换。
　　　那么逆变换呢？
　　　因为
　　　$$A[j + k] = A[j + k] + A[j + i + k] \\A[j + i + k] = A[j + k] - A[j + i + k]$$
　　　所以反过来：
　　　$$A[j + k] = \frac{A[j + k] + A[j + i + k]}{2} \\A[j + i + k] = \frac{A[j + k] - A[j + i + k]}{2}$$
　　　简单的通过两个数的和与差算出两个数本身即可。
　　　代码：
```
void FWT(LL * A, int n, int t) {
    for(register int i = 1; i < (1 << n); i <<= 1)
        for(register int p = i << 1, j = 0; j < (1 << n); j += p)
            for(register int k = 0; k < i; ++k) {
                LL x = A[j + k], y = A[i + j + k];
                A[j + k] = (x + y) % mod;
                A[i + j + k] = (x - y + mod) % mod;
                if(!t) {
                    (A[j + k] *= inv2) %= mod;
                    (A[i + j + k] *= inv2) %= mod;
                }
            }
}
```

## 3、作者的话/花絮

——远观山峦，你可以赞叹其巍岩绝壁；而登上山巅，你将能领略世间万物。
　　　　在学习$FWT|FMT$的时候，我去网上找了很多篇博客。虽然学会了模板，但是却一直不太满意。网上的教学博客多是归纳性的证明，而并非推导。我认为一个计算机理论科学爱好者并不应该止步于"看到结果"这样浅表的行为，而更应该挖掘这其中的过程，这才是计算机理论科学真正令人着迷的地方——用各种巧妙大胆的想法完成一个个看似不可能的问题。这也是完成这篇博客的初衷。
　　　　在$wiki$百科与各方博客的帮助下，这篇文章终于完成了。意在展现$FWT|FMT$精彩绝伦的推导过程，但愿你在看完这篇博客过后学到的不仅是$FWT|FMT$20行代码不到的模板。你可以尝试用同样的方法推导出$FFT$，甚至更多、更多属于你自己的运算变换。用我们无限的想象力创造出无限种可能。
　　　　　　　　　　　　　　　　　　　　　　　　　Rockdu
　　　　　　　　　　　　　　　　　　　　　　　　　2018.11.25

Rockdu's Blog

导航

最近发表

大佬们的友链