需要背的板子

这是一个大坑。

先把写到的搬上来：

void FWT_or(int *a,int flag,int len){
	for(int i=1;i<len;i<<=1){
		for(int j=0;j<len;j+=(i<<1)){
			for(int k=0;k<i;k++){
				if(flag==1){
					a[i+j+k]=(a[i+j+k]+a[j+k])%Mod;
				}
				else{
					a[i+j+k]=(a[i+j+k]-a[j+k]+Mod)%Mod;
				}
			}
		}
	}
}

void FWT_and(int *a,int flag,int len){
	for(int i=1;i<len;i<<=1){
		for(int j=0;j<len;j+=(i<<1)){
			for(int k=0;k<i;k++){
				if(flag==1){
					a[j+k]=(a[i+j+k]+a[j+k])%Mod;
				}
				else{
					a[j+k]=(a[j+k]-a[i+j+k]+Mod)%Mod;
				}
			}
		}
	}
}

void FWT_xor(int *a,int flag,int len){
	for(int i=1;i<len;i<<=1){
		for(int j=0;j<len;j+=(i<<1)){
			for(int k=0;k<i;k++){
				int Nx=a[j+k],Ny=a[i+j+k];
				a[j+k]=(Nx+Ny)%Mod;
				a[i+j+k]=(Nx-Ny+Mod)%Mod;
				if(flag==-1){
					a[j+k]=1ll*a[j+k]*inv_2%Mod;
					a[i+j+k]=1ll*a[i+j+k]*inv_2%Mod;
				}
			}
		}
	}
}

struct Complex{
	double a,r;
	friend Complex operator +(Complex a,Complex b){
		Complex ans;
		ans.a=a.a+b.a;
		ans.r=a.r+b.r;
		return ans;
	}
	friend Complex operator -(Complex a,Complex b){
		Complex ans;
		ans.a=a.a-b.a;
		ans.r=a.r-b.r;
		return ans;
	}
	friend Complex operator *(Complex a,Complex b){
		Complex ans;
		ans.a=a.a*b.a-a.r*b.r;
		ans.r=a.a*b.r+a.r*b.a;
		return ans;
	}
	friend Complex operator /(Complex a,int b){
		a.a/=b;
		a.r/=b;
		return a;
	}
	Complex(double _a=0.0,double _r=0.0){
		a=_a;
		r=_r;
	}
};
void FFT(Complex *a,int flag,int n){
	static int R[Maxn+5],last_len=0;
	int len=1,L=0;
	while(len<n){
		len<<=1;
		L++;
	}
	if(len!=last_len){
		last_len=len;
		for(int i=0;i<len;i++){
			R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
		}
	}
	for(int i=0;i<len;i++){
		if(i<R[i]){
			swap(a[i],a[R[i]]);
		}
	}
	for(int j=1;j<len;j<<=1){
		Complex T(cos(M_PI/j),flag*sin(M_PI/j));
		for(int k=0;k<len;k+=(j<<1)){
			Complex t(1,0);
			for(int l=0;l<j;l++,t=t*T){
				Complex Nx=a[k+l],Ny=t*a[j+k+l];
				a[k+l]=Nx+Ny;
				a[j+k+l]=Nx-Ny;
			}
		}
	}
	if(flag==-1){
		for(int i=0;i<len;i++){
			a[i]=a[i]/len;
		}
	}
}

void NTT(int *a,int flag,int n){
	static int R[Maxn+5],last_len=0;
	int len=1,L=0;
	while(len<n){
		len<<=1;
		L++;
	}
	if(last_len!=len){
		last_len=len;
		for(int i=0;i<len;i++){
			R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
		}
	}
	for(int i=0;i<len;i++){
		if(i<R[i]){
			swap(a[i],a[R[i]]);
		}
	}
	for(int j=1;j<len;j<<=1){
		int T=quick_power(G,(Mod-1)/(j<<1),Mod);
		for(int k=0;k<len;k+=(j<<1)){
			for(int l=0,t=1;l<j;l++,t=1ll*t*T%Mod){
				int Nx=a[k+l],Ny=1ll*t*a[j+k+l]%Mod;
				a[k+l]=(Nx+Ny)%Mod;
				a[j+k+l]=(Nx-Ny+Mod)%Mod;
			}
		}
	}
	if(flag==-1){
		reverse(a+1,a+len);
		for(int i=0,t=quick_power(len,Mod-2,Mod);i<len;i++){
			a[i]=1ll*a[i]*t%Mod;
		}
	}
}