快速沃尔什变换（FWT）

参考资料

• 快速沃尔什变换 - OI Wiki
• 沃尔什转换 - 维基百科

实现

分治递归

按位或（or）

191 Bcpp

void fmt_or(ll *a,int n,int type)
{
	if(n==1)return;
	int mid=n>>1;
	ll *a0=a,*a1=a+mid;
	fmt_or(a0,mid,type);
	fmt_or(a1,mid,type);
	for(int i=0;i<mid;i++)a1[i]=(a1[i]+a0[i]*type+mod)%mod;
}

按位与（and）

194 Bcpp

void fmt_and(ll *a,int n,int type)
{
	if(n==1)return;
	int mid=n>>1;
	ll *a0=a,*a1=a+mid;
	fmt_and(a0,mid,type);
	fmt_and(a1,mid,type);
	for(int i=0;i<mid;i++)a0[i]=(a0[i]+a1[i]*type+mod)%mod;
}

按位异或（xor）

261 Bcpp

void fwt_xor(ll *a,int n,int type)
{
	if(n==1)return;
	int mid=n>>1;
	ll *a0=a,*a1=a+mid;
	fwt_xor(a0,mid,type);
	fwt_xor(a1,mid,type);
	ll t=type==1?1:mod+1>>1;
	for(int i=0;i<mid;i++)
	{
		ll x=a0[i],y=a1[i];
		a0[i]=(x+y)*t%mod;
		a1[i]=(x-y+mod)*t%mod;
	}
}

按位同或（xnor）

264 Bcpp

void fwt_xnor(ll *a,int n,int type)
{
	if(n==1)return;
	int mid=n>>1;
	ll *a0=a,*a1=a+mid;
	fwt_xnor(a0,mid,type);
	fwt_xnor(a1,mid,type);
	ll t=type==1?1:mod+1>>1;
	for(int i=0;i<mid;i++)
	{
		ll x=a0[i],y=a1[i];
		a0[i]=(y-x+mod)*t%mod;
		a1[i]=(y+x)*t%mod;
	}
}

倍增迭代

按位或（or）

181 Bcpp

void fmt_or(ll *a,int n,int type)
{
	for(int k=1;k<n;k<<=1)
	{
		for(int i=0;i<n;i+=k<<1)
		{
			for(int j=0;j<k;j++)
			{
				a[i+j+k]=(a[i+j+k]+a[i+j]*type+mod)%mod;
			}
		}
	}
}

按位与（and）

180 Bcpp

void fmt_and(ll *a,int n,int type)
{
	for(int k=1;k<n;k<<=1)
	{
		for(int i=0;i<n;i+=k<<1)
		{
			for(int j=0;j<k;j++)
			{
				a[i+j]=(a[i+j]+a[i+j+k]*type+mod)%mod;
			}
		}
	}
}

按位异或（xor）

245 Bcpp

void fwt_xor(ll *a,int n,int type)
{
	ll t=type==1?1:mod+1>>1;
	for(int k=1;k<n;k<<=1)
	{
		for(int i=0;i<n;i+=k<<1)
		{
			for(int j=0;j<k;j++)
			{
				ll x=a[i+j],y=a[i+j+k];
				a[i+j]=(x+y)*t%mod;
				a[i+j+k]=(x-y+mod)*t%mod;
			}
		}
	}
}

按位同或（xnor）

246 Bcpp

void fwt_xnor(ll *a,int n,int type)
{
	ll t=type==1?1:mod+1>>1;
	for(int k=1;k<n;k<<=1)
	{
		for(int i=0;i<n;i+=k<<1)
		{
			for(int j=0;j<k;j++)
			{
				ll x=a[i+j],y=a[i+j+k];
				a[i+j]=(y-x+mod)*t%mod;
				a[i+j+k]=(y+x)*t%mod;
			}
		}
	}
}

高维前缀和

按位或（or）

141 Bcpp

void fmt_or(ll *a,int n,int type)
{
	for(int i=1;i<n;i<<=1)
	{
		for(int j=0;j<n;j++)
		{
			if(i&j)a[j]=(a[j]+a[i^j]*type+mod)%mod;
		}
	}
}

按位与（and）

145 Bcpp

void fmt_and(ll *a,int n,int type)
{
	for(int i=1;i<n;i<<=1)
	{
		for(int j=0;j<n;j++)
		{
			if(!(i&j))a[j]=(a[j]+a[i^j]*type+mod)%mod;
		}
	}
}

例题

洛谷 P4717 【模板】快速莫比乌斯 / 沃尔什变换 (FMT / FWT)

给定长度为 $2^n$ 的两个序列 $A,B$，设：

$$C_k=\sum_{i\oplus j=k}A_i\times B_j$$

分别当 $\oplus$ 是 $\operatorname{or},\operatorname{and},\operatorname{xor}$ 时求出 $C$。

洛谷 P6097 【模板】子集卷积

给定两个长度为 $2^n$ 的序列 $a_0,a_1,\dots,a_{2^n-1}$ 和 $b_0,b_1,\dots,b_{2^n-1}$，你需要求出一个序列 $c_0,c_1,\dots,c_{2^n-1}$，其中 $c_k$ 满足：

$$c_k=\sum_{\substack{{i \& j=0}\\{i~\mid~ j=k}}} a_i b_j$$

其中$~\mid~$表示按位或，$\&$表示按位与。

答案对 $10^9+9$ 取模。