快速沃尔什变换

参考资料

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

简介

快速沃尔什变换（Fast Walsh–Hadamard Transform，FWT）在 $O(n\log n)$ 内计算两个序列的 位运算卷积 $c_k=\sum_{i\operatorname{op}j=k}a_ib_j$，其中 $\operatorname{op}$ 为按位或、与或异或。与 FFT 类似，它把序列正变换到「点值」、逐位相乘、再逆变换还原；或、与、异或三种运算对应不同的变换，但都能用分治在 $O(n\log n)$ 内完成。

实现

分治递归

按最高位把序列分成两半递归，再按变换规则合并。

按位或（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;
			}
		}
	}
}

高维前缀和

或、与卷积本质是子集和与超集和，可直接用高维前缀和（SOS DP）按位逐维累加实现。

按位或（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$ 取模。