FWT
by AmanoKumiko
1.Or
\[A_i=∑_{j|i=i}Aj
\]
\[FWT[A]=merge(FWT[A_0],FWT[A_0]+FWT[A_1])
\]
\[UFWT[A]=merge(UFWT[A_0],UFWT[A_1]-UFWT[A_0])
\]
2.And
\[A_i=∑_{j\ and\ i=i}Aj
\]
\[FWT[A]=merge(FWT[A_0]+FWT[A_1],FWT[A_1])
\]
\[UFWT[A]=merge(UFWT[A_0]-UFWT[A_1],UFWT[A_1])
\]
3.Xor
\[i\oplus j=popcount(i\ and \ j)\ mod\ 2
\]
\[A_i=∑_{i\oplus j=0}A_j-∑_{i\oplus j=1}A_j
\]
\[FWT[A]=merge(FWT[A_0]+FWT[A_1],FWT[A_0]-FWT[A_1])
\]
\[UFWT[A]=merge(\frac{UFWT[A_0]+UFWT[A_1]}{2},\frac{UFWT[A_0]-UFWT[A_1]}{2})
\]
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);
}
}
}
}
}