作用

 

　A,B,C均为多项式。在nlogn的时间复杂度内求C=A&B,C=A|B,C=A^B;

过程

　　设A经过快速沃尔什变换后为FWT(A),FWT(C)[i]=FWT(A)[i]*FWT(B)[i];再通过FWT(C)推出C;

 

模板：https://www.luogu.org/problemnew/show/P4717

#include<cstdio>
#include<iostream>
#include<ctype.h>
using namespace std;
#define ll long long
inline ll rd()
{ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return x*f;
}
const int N=(1<<17)+13,P=998244353;
int ad(int x,int y){return x+y<P?x+y:x+y-P;}
void fwto(int *a,int n)
{for(int i=2,l=1;i<=n;i<<=1,l<<=1)for(int j=1;j<=n;j+=i)for(int k=0;k<l;k++)a[j+k+l]=ad(a[j+k+l],a[j+k]);
}
void ifwto(int *a,int n)
{for(int i=2,l=1;i<=n;i<<=1,l<<=1)for(int j=1;j<=n;j+=i)for(int k=0;k<l;k++)a[j+k+l]=ad(a[j+k+l],P-a[j+k]);
}
void fwta(int *a,int n)
{for(int i=2,l=1;i<=n;i<<=1,l<<=1)for(int j=1;j<=n;j+=i)for(int k=0;k<l;k++)a[j+k]=ad(a[j+k+l],a[j+k]);
}
void ifwta(int *a,int n)
{for(int i=2,l=1;i<=n;i<<=1,l<<=1)for(int j=1;j<=n;j+=i)for(int k=0;k<l;k++)a[j+k]=ad(P-a[j+k+l],a[j+k]);
}
int ch2(int x){return x&1?(x+P)>>1:x>>1;}
int ch(ll x,ll y){return x*y<P?x*y:x*y%P;}
void fwtx(int *a,int n)
{for(int i=2,l=1;i<=n;i<<=1,l<<=1)for(int j=1;j<=n;j+=i)for(int k=0,t;k<l;k++)t=a[j+k+l],a[j+k+l]=ad(P-t,a[j+k]),a[j+k]=ad(t,a[j+k]);
}
void ifwtx(int *a,int n)
{for(int i=2,l=1;i<=n;i<<=1,l<<=1)for(int j=1;j<=n;j+=i)for(int k=0,t;k<l;k++)t=a[j+k+l],a[j+k+l]=ch2(ad(P-t,a[j+k])),a[j+k]=ch2(ad(t,a[j+k]));
}
int a[N],b[N],c[N];
int main()
{int n=rd();n=1<<n;for(int i=1;i<=n;i++) a[i]=rd();for(int j=1;j<=n;j++) b[j]=rd();fwto(a,n);fwto(b,n);for(int i=1;i<=n;i++) c[i]=ch(a[i],b[i]);ifwto(a,n);ifwto(b,n);ifwto(c,n);for(int i=1;i<=n;i++) printf("%d ",c[i]);printf("\n");fwta(a,n);fwta(b,n);for(int i=1;i<=n;i++) c[i]=ch(a[i],b[i]);ifwta(a,n);ifwta(b,n);ifwta(c,n);for(int i=1;i<=n;i++) printf("%d ",c[i]);printf("\n");fwtx(a,n);fwtx(b,n);for(int i=1;i<=n;i++) c[i]=ch(a[i],b[i]);ifwtx(c,n);for(int i=1;i<=n;i++) printf("%d ",c[i]); 
}