FWT整理

FWT

by AmanoKumiko

1.Or

2.And

3.Xor

4.code

struct poly{
	int len;
	LL val[N];
	void Or(int opt){
		for(int mid=2;mid<len;mid<<=1){
			for(int i=0;i<len;i+=mid){
				F(j,i,i+mid/2)val[j+mid/2]+=val[j]*opt;
			}
		}
	}
	void And(int opt){
		for(int mid=2;mid<len;mid<<=1){
			for(int i=0;i<len;i+=mid){
				F(j,i,i+mid/2)val[j]+=val[j+mid/2]*opt;
			}
		}
	}
	void Xor(int opt){
		for(int mid=2;mid<len;mid<<=1){
			for(int i=0;i<len;i+=mid){
				F(j,i,i+mid/2){
					LL l=val[j],r=val[j+mid/2];
					val[j]=(l+r)/(opt==1?1:2);val[j+mid/2]=(l-r)/(opt==1?1:2);
				}
			}
		}
	}
}

FWT整理

原文：https://www.cnblogs.com/AmanoKumiko/p/15178009.html