首页 > 笔记 > FWT算法总结

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$,代码如下

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


2 COMMENTS

  1. qvq2018-02-19 下午1:22

    留名感谢博主QAQ
    以及tf/ft混用看着真不适应(逃
    另:引理证明第4个柿子最后打错了一个+-号

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×