快速沃尔什变换(FWT)
是一种可以快速完成集合卷积的算法。
什么是集合卷积啊?
集合卷积就是在集合运算下的卷积。比如一般而言我们算的卷积都是(C_i=sum_{j+k=i}A_j*B_k),而集合卷积计算的就是(C_i=sum_{jotimes k=i}A_j*B_k),其中(otimes)是一种集合运算,可以是与、或、异或。
类似于快速傅里叶变换(FFT),(FWT)也需要寻求一种变换方式(FWT(A)),使(FWT(C)=FWT(A)*FWT(B)),其中(*)运算就是数组对应下标相乘,时间复杂度是(O(n))的。
或(or)运算的FWT
构造(FWT(A)=A'),其中(A'[i]=sum_{jsubseteq i}A[j])。
这样就能满足(C'=A'*B')了。
如何构造?
考虑把(A)分成前后两段(A_0,A_1),假设(A)的长度为(2^k)。
那么(A_0)对应的二进制中第(k-1)位一定是(0),(A_1)对应的二进制中第(k-1)位一定是(1)。
所以(FWT(A)=merge(FWT(A_0),FWT(A_1)+FWT(A_0))),其中(merge)的意思是把前后两段拼接起来,因为前后两段的长度都是(2^{k-1})。
至于(IFWT?)
倒推一下就好了。(IFWT(A')=merge(IFWT(A'_0),IFWT(A'_1)-IFWT(A'_0)))。
代码:
void fwt_or(ll *P,int len,int opt){
for (int i=1;i<len;i<<=1)
for (int p=i<<1,j=0;j<len;j+=p)
for (int k=0;k<i;++k)
P[j+k+i]+=P[j+k]*opt;
}
与(and)运算的FWT
与或同理。
构造(FWT(A)=A'),(A'[i]=sum_{isubseteq j}A[j])。
(FWT(A)=merge(FWT(A_0)+FWT(A_1),FWT(A_1)))
(IFWT(A')=merge(IFWT(A'_0)-IFWT(A'_1),IFWT(A'_1)))。
代码:
void fwt_and(ll *P,int len,int opt){
for (int i=1;i<len;i<<=1)
for (int p=i<<1,j=0;j<len;j+=p)
for (int k=0;k<i;++k)
P[j+k]+=P[j+k+i]*opt;
}
异或(xor)运算的FWT
直接上结论吧。
(FWT(A)=merge(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1)))
(IFWT(A)=merge(frac{IFWT(A'_0)+IFWT(A'_1)}{2},frac{IFWT(A'_0)-IFWT(A'_1)}{2}))。
证明出门右转
代码:
void fwt(int *P,int len,int opt){
for (int i=1;i<len;i<<=1)
for (int p=i<<1,j=0;j<len;j+=p)
for (int k=0;k<i;++k)
{
int x=P[j+k],y=P[j+k+i];
P[j+k]=1ll*opt*(x+y)%mod;
P[j+k+i]=1ll*opt*(x-y+mod)%mod;
}
}
如果是(IFWT)的话就让(opt=frac{mod+1}2)就好了。