【学习笔记】快速沃尔什变换

快速沃尔什变换(FWT)是一种广义上的傅里叶变换,可以解决子集并卷积子集交卷积以及子集对称差卷积

而在OI中决定了FWT胜过FMT的一大原因就是他可以方便地解决子集对称差卷积,即:

其中$\oplus$表示二进制数的异或运算、集合的对称差运算(虽然”对称差”听起来挺有道理,但是感觉“二进制非进位加法”更有趣)。


再谈线性变换实质

首先是构造,我们考虑线性变换的本质,需要有:

那么一个思路就是先设一个辅助函数$\varphi(i,x)$出来:

那么就会有:

然后把

带进去并调整:

发现 $\sum_{p\geq 0}\sum _{q\geq 0}a_pb_q$ 是可以消掉的,于是就有:

构造$\varphi$

对于异或操作来说,异或前后$1$的个数的奇偶性不会改变。即也就是说$i,j$中$1$的个数加起来和$i\oplus j$中1的个数的奇偶性是一样的。形式化地讲:

证明:

考虑$i \oplus j$的每一位:

  • 若$i$和$j$的这一位相同,那么就会变成$0$,$1$的个数减二或不变;
  • 如不同,那么就一定是$(xx1xx)\oplus(xx0xx)=(xx1xx)$,$1$的个数还是不变。

而我们发现这个引理解决的是相加不变的问题,而我们需要的$\varphi$函数需要满足相乘不变,于是自然而然地想到要放到幂上去。

于是就定义了$\varphi$:

换成数值的表示方法:

这么定义的原因是:

异或对交有分配律,那么:

于是就喜提一个指数级算法

真正的$\rm{FWT}$

我们发现似乎这东西没有办法dp,于是考虑:

每一次考虑新加入第$i$个物品取不取的情况,将当前集合分为$i$取和$i$不取,$i$取的放右边,$i$不取的放左边。

$i$取的话,和$i$取的状态取并后集合大小不变,和$i$不取的状态取并后集合大小$−1$。$i$不取的话,和$i$取的状态取并后集合大小不变,和$i$不取的状态取并后集合大小同样的不变。

这样考虑原有状态,左右两边对$i$不取的贡献都是$\text{++}$,因为集合大小不变。左边对$i$取的贡献是$+$,右边对$i$取的贡献是$\text{−−}$,因为都取$i$的话并集增加了$1$,贡献取反。

然后其实就是个模拟的思路,由于$(1xxxxxx)_2$和$(0xxxxxx)_2$的数量是一致的,所以我们可以将小于$(1000000)_2$的分为一类,大于等于$(1000000)_2$的分为一类,从数值上看就是前一半和后一半。

总之就是个FFT🦋操作的思路啦。

然后对于逆变换,因为我们刚才的结论有:

所以我们现在为了得到原来的$F[i+j+k]$和$F[j+k]$,直接

1
2
3
4
5
6
7
8
9
10
void fwt(int *f, int g){
int i, j, k, m = 1 << (N - 1), x, y ;
for (i = 1 ; i <= m ; i <<= 1)
for (j = 0 ; j <= M ; j += (i << 1))
for (k = 0 ; k < i ; ++ k){
x = f[j + k], y = f[i + j + k] ;
f[j + k] = 1ll * (g ^ 1 ? Inv2 : 1) * (x + y) % Mod ;
f[i + j + k] = 1ll * (g ^ 1 ? Inv2 : 1) * (x + Mod - y) % Mod ;
}
}

于是时间复杂度就是$n \log n$了。

$\rm FWT$做or/and卷积

艹,真是被血坑了。

才发现原来FWT做or/and卷积就是跟FMT一个道理:

然后逆变换就直接把加号改成减号就好了……原因就是“不取这个东西”一定是“取这个东西”的子集。

但是当时我认真学习FMT的时候,Rockdu博客里面FMT的代码是FWT的!!!然后再看别人的代码我就懵O了好久……

真是zz

但是终于理解了JOHNKRAM神仙的话:

不得不说是很形象了。

后记

  • 其实Lugou上的板子的复杂度是$2^n n$的,我一开始就觉得暴力枚举子集没啥问题,结果最后发现枚举子集不是枚举$(n)_2$的子集,而是枚举$(2^n)_2$的子集……白学了白学了
  • 唉,本来就是功能相同的FWT和FMT,看错代码真是GG
  • 其实只有对称差卷积难理解一些,交并卷积都是很形象的。