【模板/经典题型】FWT

时间：2022-12-06 21:15:37

FWT在三种位运算下都满足FWT(a×b)=FWT(a)*FWT(b)

其中or卷积和and卷积还可以通过FMT实现（本质上就是个高维前缀和）

#include<bits/stdc++.h>

#define N 1100000

#define eps 1e-7

#define inf 1e9+7

#define db double

#define ll long long

#define ldb long double

using namespace std;

inline int read()

{

	char ch=0;

	int x=0,flag=1;

	while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}

	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*flag;

}

const ll mo=998244353;

int ksm(int x,int k)

{

	int ans=1;

	while(k)

	{

		if(k&1)ans=1ll*ans*x%mo;

		k>>=1;x=1ll*x*x%mo;

	}

	return ans;

}

void fwt_or(int *f,int n,int flag)

{

	for(int k=2,kk=1;k<=(1<<n);k<<=1,kk<<=1)

	  for(int i=0;i<(1<<n);i+=k)

	    for(int j=0;j<kk;j++)

		f[i+j+kk]=(f[i+j+kk]+flag*f[i+j])%mo;

}

void fwt_and(int *f,int n,int flag)

{

	for(int k=2,kk=1;k<=(1<<n);k<<=1,kk<<=1)

	  for(int i=0;i<(1<<n);i+=k)

	    for(int j=0;j<kk;j++)

		f[i+j]=(f[i+j]+flag*f[i+j+kk])%mo;

}

void fwt_xor(int *f,int n,int flag)

{

	for(int k=2,kk=1;k<=(1<<n);k<<=1,kk<<=1)

	  for(int i=0;i<(1<<n);i+=k)

	    for(int j=0;j<kk;j++)

		{

			int t=f[i+j+kk];

			f[i+j+kk]=(f[i+j]-t+mo)%mo;

			f[i+j]=(f[i+j]+t)%mo;

		}

	if(flag==-1)

	{

		int inv=ksm(1<<n,mo-2);

		for(int i=0;i<(1<<n);i++)f[i]=1ll*f[i]*inv%mo;

	}

}

int a[N],b[N];

void Or(int n)

{

	fwt_or(a,n,+1);fwt_or(b,n,+1);

	for(int i=0;i<(1<<n);i++)a[i]=1ll*a[i]*b[i]%mo;

	fwt_or(a,n,-1);

}

void And(int n)

{

	fwt_and(a,n,+1);fwt_and(b,n,+1);

	for(int i=0;i<(1<<n);i++)a[i]=1ll*a[i]*b[i]%mo;

	fwt_and(a,n,-1);

}

void Xor(int n)

{

	fwt_xor(a,n,+1);fwt_xor(b,n,+1);

	for(int i=0;i<(1<<n);i++)a[i]=1ll*a[i]*b[i]%mo;

	fwt_xor(a,n,-1);

}

int A[N],B[N];

int main()

{

	int n=read();

	for(int i=0;i<(1<<n);i++)A[i]=read();

	for(int i=0;i<(1<<n);i++)B[i]=read();

	for(int i=0;i<(1<<n);i++)a[i]=A[i],b[i]=B[i];

	Or(n);for(int i=0;i<(1<<n);i++)printf("%lld ",(a[i]%mo+mo)%mo);printf("\n");

	for(int i=0;i<(1<<n);i++)a[i]=A[i],b[i]=B[i];

	And(n);for(int i=0;i<(1<<n);i++)printf("%lld ",(a[i]%mo+mo)%mo);printf("\n");

	for(int i=0;i<(1<<n);i++)a[i]=A[i],b[i]=B[i];

	Xor(n);for(int i=0;i<(1<<n);i++)printf("%lld ",(a[i]%mo+mo)%mo);printf("\n");

	return 0;

}

相关文章