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

作者: shad0w_walker(admin) 分类: 算法 发布时间: 2016-08-12 02:53 ė 6 没有评论

昨天打了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卷积。

 

本文出自shad0w_walker,转载时请注明出处及相应链接。

本文永久链接: https://www.sdwalker.com/archives/493.html

0 ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

返回顶部