fwt模版

void FWT(int a[],int n,int _k){ for(int m=2;m<=n;m<<=1) for(int i=0;i<=n-1;i+=m) for(int j=0;j<=m/2-1;j++){ int t0=a[i+j], t1=a[i+j+m/2]; if(_k==1){ a[i+j]=(t0+t1)%mod,a[i+j+m/2]=(t0-t1+mod)%mod; //xor:a[i+j]=(t0+t1)%mod,a[i+j+m/2]=(t0-t1+mod)%mod; //and:a[i+j]=t0+t1; //or:a[i+j+m/2]=t0+t1; } else{ a[i+j]=1ll*(t0+t1)*rev2%mod,a[i+j+m/2]=1ll*(t0-t1+mod)%mod*rev2%mod; //xor:a[i+j]=(t0+t1)/2,a[i+j+m/2]=(t0-t1)/2; //and:a[i+j]=t0-t1; //or:a[i+j+m/2]=t1-t0; } } }