发布于

lp4717 【模板】快速沃尔什变换

快速沃尔什变换是一种类似于快速傅里叶变换的操作。它是用来处理子集卷积的有效工具。
我们依次考虑操作符为and or或者xor时的情况。
我们如是考虑：将一个长度为\(2^n\)的数列\(A_{0}\)和\(A_{1}\)切割成两个长度为\(2^{n-1}\)的部分，\(A_{0}\)表示下标最高位为0的数列，而\(A_{1}\)表示下标最高位1的数列。
那么，我们有很显然的and的式子：
$$ C_{0}=A_{0} * B_{0}$$ $$ C_{1}=A_{0} * B_{1} + A_{1} * B_{0} + A_{1} * B_{1}=(A_{0} + A_{1})*(B_{0} + B_{1}) – C_{0}$$
同理，我们可以得到or的式子。
$$C_{0}=A_{0} * B_{0} + A_{1} * B_{0} + A_{0} * B_{1} = (A_{0} + A_{1}) * (B_{0} + B_{1}) -C_{1}$$ $$C_{1}=A_{1} * B_{1}$$
以及xor的式子：
$$C_{0} = A_{0} * B_{0} + A_{1} * B_{1}$$ $$C_{1} = A_{0} * B_{1} + A_{1} * B_{0}$$
我们发现，除了xor以外的式子，都是「简洁」的。
换而言之，我们可以直接以\(nlog_n\)的复杂度求得它们的答案。
现在考虑xor这个玄妙的式子。
我们发现有如下性质：
$$C_{0} + C_{1} = (A_{0} + A_{1}) * (B_{0} + B_{1})$$ $$C_{0} – C_{1} = (A_{0} – A_{1}) * (B_{0} – B_{1})$$
我们不妨令：
$$X = (A_{0} + A_{1}) * (B_{0} + B_{1})$$ $$Y = (A_{0} – A_{1}) * (B_{0} – B_{1})$$
那么
$$ C_{0} = \frac{X + Y}{2}$$ $$ C_{1} = \frac{X – Y}{2}$$
于是就做完了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

typedef long long ll;
const ll MOD=998244353;
const ll inv2=(MOD+1)>>1;
inline void fwtor(int *A,int *B,int *C,int N){
	if(N==1){
		C[0]=1ll*A[0]*B[0]%MOD;return;
	}
	int M=N>>1;
	for(int i=0;i<M;++i){
		A[i+M]+=A[i];A[i+M]%=MOD;
		B[i+M]+=B[i];B[i+M]%=MOD;
	}
	fwtor(A,B,C,M);fwtor(A+M,B+M,C+M,M);
	for(int i=0;i<M;++i){
		C[i+M]-=C[i]-MOD;C[i+M]%=MOD;
	}
}
inline void fwtand(int *A,int *B,int *C,int N){
	if(N==1){
		C[0]=1ll*A[0]*B[0]%MOD;return;
	}
	int M=N>>1;
	for(int i=0;i<M;++i){
		A[i]+=A[i+M];A[i]%=MOD;
		B[i]+=B[i+M];B[i]%=MOD;
	}
	fwtand(A,B,C,M);fwtand(A+M,B+M,C+M,M);
	for(int i=0;i<M;++i){
		C[i]-=C[i+M]-MOD;C[i]%=MOD;
	}
}
inline void fwtxor(int *A,int *B,int *C,int N){
	if(N==1){
		C[0]=1ll*A[0]*B[0]%MOD;return;
	}
	int M=N>>1,XA,YA,XB,YB;
	for(int i=0;i<M;++i){
		XA=(A[i]+A[i+M])%MOD,YA=(A[i]-A[i+M]+MOD)%MOD;
		XB=(B[i]+B[i+M])%MOD,YB=(B[i]-B[i+M]+MOD)%MOD;
		A[i]=XA,A[i+M]=YA,B[i]=XB,B[i+M]=YB;
	}
	fwtxor(A,B,C,M),fwtxor(A+M,B+M,C+M,M);
	for(int i=0;i<M;++i){
		XA=(C[i]+C[i+M])%MOD,YA=(C[i]-C[i+M]+MOD)%MOD;
		C[i]=XA*inv2%MOD,C[i+M]=YA*inv2%MOD;
	}
}
int n;
int a[1<<17],b[1<<17],c[1<<17],aa[1<<17],bb[1<<17];
void init(){
	scanf("%d",&n);
	n=1<<n;
	for(int i=0;i<n;++i)scanf("%d",a+i);
	for(int i=0;i<n;++i)scanf("%d",b+i);
	for(int i=0;i<n;++i)aa[i]=a[i],bb[i]=b[i],c[i]=0;
	fwtor(aa,bb,c,n);
	for(int i=0;i<n;++i)printf("%d ",c[i]);puts("");
	for(int i=0;i<n;++i)aa[i]=a[i],bb[i]=b[i],c[i]=0;
	fwtand(aa,bb,c,n);
	for(int i=0;i<n;++i)printf("%d ",c[i]);puts("");
	for(int i=0;i<n;++i)aa[i]=a[i],bb[i]=b[i],c[i]=0;
	fwtxor(aa,bb,c,n);
	for(int i=0;i<n;++i)printf("%d ",c[i]);puts("");
}
int main(){
	init();
	return 0;
}