FWT

FWT

一、用途

一般的\(FFT\)做的是形如\(F_k=\sum_{i+j=k}g_ih_j\)的卷积，但如果我们遇到的是其他的操作符呢？

比如说：

\[C_k=\sum_{i|j=k}A_iB_j\\ C_k=\sum_{i\&j=k}A_iB_j\\ C_k=\sum_{i\text{^} j=k}A_iB_j \]

如果运算符从不同的加法变成了位运算，该怎样做？

答案是——FWT。

二、实现方式

考虑\(FFT\)，我们通过对多项式求出它在特殊位置的点值然和将点值相乘，最后复原

那么我们同样希望对于位运算卷积也能通过某种方式转化为点值相乘，也就是将\(A\)转化为\(FWT(A)\)，然后直接将\(FWT(A)\)与\(FWT(B)\)相乘得到\(FWT(C)\)，最后再还原。

那么如何得到这个\(FWT\)多项式呢，我们依次考虑这三个不同的位运算：

（一）或卷积

即\(C_k=\sum_{i|j=k}A_iB_j\)

因为\(i|j=k\)，所以说\(i\)中二进制中为\(1\)的位置与\(j\)二进制位\(1\)的位置一定是\(k\)中的位置的子集。

于是我们可以构造出:

\[FWT(A)[i]=\sum_{j|i=i}A[j] \]

即满足二进制中为\(1\)的位置是\(i\)的子集的所有\(j\)的集合

那么易证：

\[\begin{aligned} FWT(C)[i]&=\sum_{j|i=i}C[j]\\&=\sum_{j|i=i}\sum_{x|y=j}A[x]B[y]\\ &=\sum_{(x|y)|i=i}A[x]B[y]\\ &=\sum_{x|i=i}A[x]\sum_{y|i=i}B[y] \end{aligned} \]

于是这个构造是可行的。

构造是有了，那么如何快速求出\(FWT(f)\)呢?

考虑将\(A\)这个区间分成，下标二进制下最高位为\(0\)的部分\(A_0\)，与最高位为\(1\)的部分\(A_1\)

那么根据定义容易得到：

\[FWT(A)=merge(FWT(A_0),FWT(A_0)+FWT(A_1)) \]

其中\(merge\)是像字符串拼接一样将它拼起来的过程

还原就反过来就行了：

\[UFWT(A)=merge(UFWT(A_0),UFWT(A_1)-UFWT(A_0)) \]

（二）与卷积

类比可得：

\[FWT(A)[i]=\sum_{j\&i=i}A[j] \]

\[FWT(A)=merge(FWT(A_0)+FWT(A_1),FWT(A_1)) \]

\[UFWT(A)=merge(UFWT(A_0)-UFWT(A_1),UFWT(A_1)) \]

inline void FWT_and(int *f,int tp,int tot){
	for(int i=1;i<tot;i<<=1)
		for(int j=0;j<tot;j+=(i<<1))
			for(int k=0;k<i;++k){
				if(tp==1) f[j+k]=add(f[j+k],f[j+i+k]);
				else f[j+k]=dec(f[j+k],f[j+i+k]);
			}
}

（三）异或卷积

异或运算是最常考，也是相对较难的运算：

这个运算的公式我太不会推，这里先给出结论，然后尝试证明：

定义\(i\otimes j\)为\(i\&j\)的二进制下\(1\)的数量的奇偶性：

\[FWT(A)[i]=\sum_{i\otimes j=0}A_j-\sum_{i\otimes j=1}A_j \]

证明：

\[\begin{aligned} FWT(C)[i]&=FWT(A)[i]FWT(B)[i]\\&=(\sum_{i\otimes j=0}A_j-\sum_{i\otimes j=1}A_j)(\sum_{i\otimes k=0}B_k-\sum_{i\otimes k=1}B_k)\\ &=(\sum_{i\otimes j=0}\sum_{i\otimes k=0}A_jB_k)+(\sum_{i\otimes j=1}\sum_{i\otimes k=1}A_jB_k)-(\sum_{i\otimes j=0}\sum_{i\otimes k=1}A_jB_k)-(\sum_{i\otimes j=1}\sum_{i\otimes k=0}A_jB_k)\\ &=\sum_{(i\otimes (j\ xor\ k)=0)}A_jB_k-\sum_{(i\otimes (j\ xor\ k)=1)}A_jB_k\\ &=\sum_{i\otimes j=0}C_j-\sum_{i\otimes j=1}C_j \end{aligned} \]

于是我们就有：

\[FWT(A)=merge(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1)) \]

\[UFWT(A)=merge(\frac{UFWT(A_0)+UFWT(A_1)}{2},\frac{UFWT(A_0)-UFWT(A_1)}{2}) \]

inline void FWT_xor(int *f,int tp,int tot){
	for(int i=1;i<tot;i<<=1)
		for(int j=0;j<tot;j+=(i<<1))
			for(int k=0;k<i;++k){
				int x=f[j+k],y=f[j+i+k];
				if(tp==1) f[j+k]=add(x,y),f[j+i+k]=dec(x,y);
				else f[j+k]=1ll*iv2*add(x,y)%mod,f[j+i+k]=1ll*iv2*dec(x,y)%mod;
			}
}

大家可以去尝试一下这道例题，套模板就行了。

（四）子集卷积

子集卷积求的是

\[c_k=\sum_{i\& j=0,i|j=k}a_ib_j \]

子集卷积相比普通的或卷积增加了一个 \(i\&j=0\) 的条件，这个条件就相当于 \(|i|+|j|=|k|\)，因此我们可以多记一维表示该集合的大小，设 \(f_{i,j}=[|j|=i]a_j,g_{i,j}=[|j|=i]b_j\)，那么原问题即相当于求：

\[h_{i,j}=\sum_{k<i}\sum_{A|B=j}f_{k,A}g_{i-k,B} \]

于是就可以通过 \(\mathcal O(n)\) 次 FWT 求解了，复杂度为 \(\mathcal O(2^nn^2)\)。

#include<bits/stdc++.h>
using namespace std;
const int N=(1<<20)+10;
const int mod=1e9+9;
int n,a[21][N],b[21][N],c[21][N],siz[N],lim;
inline int add(int x,int y){return (x+y>=mod)?x+y-mod:x+y;}
inline int dec(int x,int y){return (x-y<0)?x-y+mod:x-y;}
inline void FMT(int n,int *f,int tp){
	for(int i=0;i<n;++i)
		for(int j=0;j<lim;++j)
			if(j&(1<<i)){
				if(tp==1) f[j]=add(f[j],f[j^(1<<i)]);
				else f[j]=dec(f[j],f[j^(1<<i)]);
			}
} 
int main(){
	scanf("%d",&n);lim=1<<n; 
	for(int i=0;i<n;++i)
		for(int j=0;j<lim;++j)
			if(j&(1<<i)) ++siz[j];
	for(int i=0;i<lim;++i) scanf("%d",&a[siz[i]][i]);
	for(int i=0;i<lim;++i) scanf("%d",&b[siz[i]][i]);
	for(int i=0;i<=n;++i){
		FMT(n,a[i],1);FMT(n,b[i],1);
		for(int j=0;j<lim;++j)
			for(int k=0;k<=i;++k)
				c[i][j]=add(c[i][j],1ll*a[k][j]*b[i-k][j]%mod);
	}
	for(int i=0;i<=n;++i) FMT(n,c[i],-1);
	for(int i=0;i<lim;++i) printf("%d ",c[siz[i]][i]);
	return 0;
}