奇奇怪怪的卷积与快速沃尔什变换

昨天打了2016多校的第八场，1003赛中写了暴力TLE卡了一直没过，赛后看题解说是什么or卷积，标程里面玄学的fwt和ifwt函数完全看不懂，于是赶快补了下这方面的知识，趁脑袋还热乎记点东西下来。

---

所谓的卷积啊就是这个玩意\(\int_{-\infty }^{\infty }f(\tau )g(x-\tau )d\tau\)，在信号处理里有广泛的用处，但是这并不妨碍数学家乐此不疲的玩它啊。具体卷积的数学含义以及在工程中的用途这里就不细讲了，请自行搜索“卷积”。

对于两个离散的序列f和g，设他们的卷积是h，那么卷积的定义就是\(h[x]=\sum_{t=0}^{n}f[t]g[x-t]\)。也就是说对于一个f[i]和一个g[j]，它们的乘积会贡献给h[i+j]。所以我们在计算f和g的卷积时就可以这样计算：

for(i=0;i<n;i++) for(j=0;j<n;j++) h[i+j]+=f[i]*g[j];

这样的计算卷积的复杂度显然是\(O(n^{2})\)的，在大多数情况下都不能满足时限要求，相信地球人都知道，我要引出一个强大的工具——快速傅里叶变换(FFT)，通过FFT我们能将计算卷积的复杂度降至\(O(n\log n)\)：

FFT(a,lena,1);//对a数组进行FFT

FFT(b,lenb,1);//对b数组进行FFT

for(i=0;i<lenc;i++) c[i]=a[i]*b[i];//a和b数组相乘

FFT(c,lenc,-1);//对c数组进行FFT逆变换

在这里对快速傅里叶变换也不做详细介绍了，请自行搜索“快速傅里叶变换”。

为什么FFT能降低复杂度呢，因为FFT具有这样的性质FFT(A*B)=FFT(A)*FFT(B)，所以能够将A、B数组进行FFT后两两相乘得到AB卷积的FFT结果。

对于普通的卷积，f[i]*g[j]贡献给了h[i+j]，接下来我们来看这样一个卷积——f[i]*g[j]贡献给h[i xor j]，也就是

for(i=0;i<n;i++) for(j=0;j<n;j++) h[i^j]+=f[i]*g[j];

设这个卷积用符号表示为$，为了解决这个xor卷积，我们可以模仿FFT构造一个变换，我们暂时称这个变换为tf，它的逆变换为utf，那么与FFT相似，它需要满足这些条件：

1、utf( tf(X) ) = X

2、tf(X$Y) = tf(X) * tf(Y)

 

考虑一个二元情况：

X = (a, b)，Y = (c, d)，那他们的卷积X$Y = Z = (z0, z1)，因为是xor卷积，所以

z0 = (a*c) + (b*d)

z1 = (a*d) + (b*c)

接下来验证tf(a, b) = (a-b, a+b)成立

tf(a,b) * tf(c,d)

= (a – b, a + b) * (c – d, c + d)

= ( (a-b)*(c-d) , (a+b)*(c+d) )

= ( ac – ad – bc + bd, ac + ad + bc + bd )

= ( ac + bd – ad – bc, ac + bd + ad + bc )

= tf( ac + bd, ad + bc )

= tf( (a,b) $ (c,d ) )

所以，对于二元情况，这个tf能够满足。如果是对于两个向量X1,X2，同样可以证明：

tf(X1,X2) = (tf(X1) – tf(X2), tf(X1) + tf(X2))

看到这里大概就懂了，这个tf(a, b) = (a-b, a+b)就相当于普通卷积中的傅里叶变换，利用它使得上面的条件2成立，就能处理xor卷积问题，这个变换据说叫沃尔什变换。以上的证明不够详细，如果想看详细的证明可以点这里的NIM这道题SRM 518 – TopCoder Wiki

接下来考虑tf的逆变换utf，由tf的变换式很容易得到utf(a, b) = ( (a+b)/2, (b-a)/2 )，这应该不难理解了。

 

具体实现，因为tf对二元向量形式成立，所以可以用分治来处理，顺便就叫他快速沃尔什变换（fwt）吧！具体的操作如下：

 

昨天遇到的题目用的是or卷积，or卷积和上面的xor卷积其实内容差不多，直接给出结论：or卷积的tf为tf(a, b) = (a, a+b)，同时逆变换utf(a, b) = (a, b-a)，证明和xor卷积几乎一样。

附上这道题color II，题目是对于给定的无向图，求出所有子图的图着色最小颜色数。具体做法就是先求出每个子图是否是独立集du[i]，对于f[i][j]，表示i个独立集即i种颜色染状态为j的子图的方案数，每次i增加1，就是将du与f[i]做一次or卷积。