其实FWT我啥都不会，反正就是记一波结论，记住就好……
具体证明的话，推荐博客：FWT快速沃尔什变换学习笔记
现有一些卷积，形如
\(C_k=\sum\limits_{i\lor j=k}A_i*B_j\)
\(C_k=\sum\limits_{i\land j=k}A_i*B_j\)
\(C_k=\sum\limits_{i\oplus j=k}A_i*B_j\)
然后普通的FFT肯定应付不了这玩意，于是就有了FWT(快速沃尔什变换)，然后我就直接写结论好了……
FWT——Or卷积
我们把多项式\(A\)(\(2^n\)项)拆成两部分\(A_0,A_1\)，则有
\[FWT(A)=\begin{cases}(FWT(A_0),FWT(A_0+A_1))&,n>0\\A&,n=0\end{cases}
\]
\]
然后上面的部分是指两部分合到一块儿
然后再给个性质
\[FWT(A)_i=\sum\limits_{j\lor i=i}A_j
\]
\]
所以说统计子集和啥的就直接FWT一下就好了，还有个叫FMT(快速莫比乌斯变换)的，其实就是这玩意
FWT——And卷积
同样将多项式\(A\)拆开，有
\[FWT(A)=\begin{cases}(FWT(A_0+A_1),FWT(A_1))&,n>0\\A&,n=0\end{cases}
\]
\]
其实你发现和Or卷积差不多，咋记呢？你看\(A_0,A_1\)的差别就在最高位，然后Or(\(\lor\))肯定是答案贡献到1上去了，所以是后面加，然后And(\(\land\))就反过来，然后就这么记吧……
同样的，这个卷积也有个性质
\[FWT(A)_i=\sum\limits_{j\land i=i}A_j
\]
\]
这就相当于统计超集和了……
FWT——Xor卷积
这个东西还是要记一下的……
\[FWT(A)=\begin{cases}(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1))&,n>0\\A&,n=0\end{cases}
\]
\]
然后这个貌似没有那啥奇怪性质……
FWT讲完了，但是你不变换回来没啥用的啊……所以显然也要有IFWT
然后IFWT也比较简单
\[\lor :IFWT(A)=(IFWT(A_0),IFWT(A_1)-IFWT(A_0))
\]
\]
\[\land :IFWT(A)=(IFWT(A_0)-IFWT(A_1),IFWT(A_1))
\]
\]
\[\oplus :IFWT(A)=(\dfrac{IFWT(A_0)+IFWT(A_1)}{2},\dfrac{IFWT(A_0)-IFWT(A_1)}{2})
\]
\]
然后贴个板子好了……
void div(int &x){x=1ll*x*inv%p;}
void FWT_xor(int *a,int n,int type){
for (int i=2;i<=n;i<<=1){
for (int j=0;j<n;j+=i){
for (int k=0;k<i>>1;k++){
int x=a[j+k],y=a[j+k+(i>>1)];
a[j+k]=(x+y)%p,a[j+k+(i>>1)]=(x-y+p)%p;
if (!~type) div(a[j+k]),div(a[j+k+(i>>1)]);
}
}
}
}
void FWT_and(int *a,int n,int type){
for (int i=2;i<=n;i<<=1){
for (int j=0;j<n;j+=i){
for (int k=0;k<i>>1;k++){
(a[j+k]+=type*a[j+k+(i>>1)])%=p;
if (a[j+k]<0) a[j+k]+=p;
}
}
}
}
void FWT_or(int *a,int n,int type){
for (int i=2;i<=n;i<<=1){
for (int j=0;j<n;j+=i){
for (int k=0;k<i>>1;k++){
(a[j+k+(i>>1)]+=type*a[j+k])%=p;
if (a[j+k+(i>>1)]<0) a[j+k+(i>>1)]+=p;
}
}
}
}