快速沃尔什变换

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

而在OI中决定了FWT胜过FMT的一大原因就是他可以方便地解决子集对称差卷积,即:
$$
c_i=\sum_{j\oplus k=i} a_jb_k
$$
其中$\oplus$表示二进制数的异或运算、集合的对称差运算(虽然”对称差”听起来挺有道理,但是感觉“二进制非进位加法”更有趣)。


再谈线性变换实质

首先是构造,我们考虑线性变换的本质,需要有:
$$
{\rm FWT(C)}_i={\rm FWT(B)}_i\cdot{\rm FWT(A)}_i
$$
那么一个思路就是先设一个辅助函数$\varphi(i,x)$出来:
$$
{\rm FWT(F)}_i=\sum_{j\geq 0}\varphi(j,i) \cdot f_j
$$
那么就会有:
$$
\sum_{j\geq 0}\varphi(j,i) \cdot c_j=\sum_{j\geq 0}\varphi(j,i) \cdot a_j\times \sum_{j\geq 0}\varphi(j,i) \cdot b_j
$$
然后把$c_i=\sum_{j\oplus k=i} a_jb_k$带进去并调整:
$$
\begin{aligned}
\sum_{j\geq 0}\varphi(j,i) \cdot \sum_{p\oplus q=j} a_pb_q & =\sum_{j\geq 0}\varphi(j,i) \cdot a_j \times\sum_{j\geq 0}\varphi(j,i) \cdot b_j\\\
\sum_{p \geq 0} \sum_{q\geq 0}\varphi(p\oplus q,i)\cdot a_pb_q & =\sum_{p\geq 0}\sum_{q\geq 0}\varphi(p,i) \cdot \varphi(q,i)\cdot a_pb_q\\\
\end{aligned}
$$
发现$\sum_{p\geq 0}\sum _{q\geq 0}a_pb_q$是可以消掉的,于是就有:
$$
\varphi(p\oplus q,i)=\varphi(p,i)\cdot \varphi(q,i)
$$

构造$\varphi$

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

$$
\rm bitcount(i)+bitcount(j)\equiv bitcount(i~\oplus ~j)~(\bmod 2)
$$

证明:

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

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

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

于是就定义了$\varphi$:
$$
\varphi(s,t)=(-1)^{|s\cap t|}
$$
换成数值的表示方法:
$$
\varphi(i,j)=(-1)^{\rm bitcount \mathcal{(i ~\rm{and}~ j)}}
$$
这么定义的原因是:
$$
(i \cap x) \oplus(j \cap x)=(i \oplus j) \cap x
$$
异或对交有分配律,那么:

$$
{\rm{FWT(F)}}_i=\sum_{j \geq 0}(-1)^{|i\cap j|}f_j
$$

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

真正的$\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🦋操作的思路啦。

然后对于逆变换,因为我们刚才的结论有:
$$
\begin{aligned}{F[j+k] =F[j+k]+F[i+j+k]} \\ {F[i+j+k]=F[j+k]-F[i+j+k]}\end{aligned}
$$
所以我们现在为了得到原来的$F[i+j+k]$和$F[j+k]$,直接
$$
\begin{array}{c}{F[j+k]=\frac{F[j+k]+F[j+i+k]}{2}} \ {F[j+i+k]=\frac{F[j+k]-F[j+i+k]}{2}}\end{array}
$$

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一个道理:
$$
\boldsymbol{or}: F[i+j+k]+=F[j+k]\\\
\boldsymbol{and}: F[j+k]+=F[i+j+k]
$$
然后逆变换就直接把加号改成减号就好了……原因就是“不取这个东西”一定是“取这个东西”的子集。

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

真是zz

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

不得不说是很形象了。

后记

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