奇奇怪怪的卷积与快速沃尔什变换
昨天打了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)吧!具体的操作如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
const int mod=1e9+7; int Inv2=qpow(2,mod-2); void fwt(int l,int r,int a[])//fwt变换 { if(l==r-1) return; int len=(r-l)>>1; int m=l+len; fwt(l,m,a); fwt(m,r,a); for(int i=l;i<m;i++){ long long x1=a[i],x2=a[i+len]; a[i]=(x1-x2+mod)%mod; a[i+len]=(x1+x2)%mod; } } void ifwt(int l,int r,int a[])//fwt逆变换 { if(l==r-1) return; int len=(r-l)>>1; int m=l+len; for(int i=l;i<m;i++){ long long y1=a[i],y2=a[i+len]; a[i]=(y1+y2)*Inv2%mod;//Inv2为2对mod的逆元 a[i+len]=(y2-y1+mod)*Inv2%mod; } ifwt(l,m,a); ifwt(m,r,a); } |
昨天遇到的题目用的是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