快速沃尔什变换FWT-快速莫比乌斯变换FMT-学习笔记-个人总结

## FWT 思想和FFT很类似，FFT是把一个多项式变成点值表达，然后就可以按位直接相乘，然后再逆变换回去。而FWT是把一个数组通过变换，使得可以按位相乘，然后再变换回去。 [RabbitHu](https://www.cnblogs.com/RabbitHu/p/9182047.html) [yyb](https://www.cnblogs.com/cjyyb/p/9065615.html) 博客上有很详细的证明，~~然而我也不会，我只会背板~~ 对于OR： $tf(A) = (tf(A_0), tf(A_1) + tf(A_0))$ $utf(A) = (utf(A), utf(A_1) - utf(A_0))$ AND： $tf(A) = (tf(A_0) + tf(A_1), tf(A_1))$ $utf(A) = (utf(A_0) - utf(A_1), utf(A_1))$ XOR： $tf(A) = (tf(A_0) + tf(A_1), tf(A_0) - tf(A_1))$ $utf(A) = (\frac{utf(A_0) + utf(A_1)}{2}, \frac{utf(A_0) - utf(A_1)}{2})$ **XOR记得每次都要除2** ```cpp int A[N],B[N],a[N],b[N],c[N]; void fwtor(int f[],LL op) { for(ri p=2; p<=n; p<<=1) { int len=p>>1; for(ri k=0; k<n; k+=p) for(ri i=k; i<k+len; ++i) f[i+len]=(f[i+len]+op*f[i]+md)%md; } } const int inv2=(md+1)/2; void fwtand(int f[],LL op) { for(ri p=2; p<=n; p<<=1) { int len=p>>1; for(ri k=0; k<n; k+=p) for(ri i=k; i<k+len; ++i) f[i]=(f[i]+op*f[i+len]+md)%md; } } void fwtxor(int f[],int op) { for(ri p=2; p<=n; p<<=1) { int len=p>>1; for(ri k=0; k<n; k+=p) for(ri i=k; i<k+len; ++i) { int t=f[i+len]; f[i+len]=(f[i]-f[i+len]+md)%md; f[i]=(f[i]+t)%md; } if(op==-1) for(ri i=0; i<n; ++i) f[i]=(LL)f[i]*inv2%md; } } void calcor() { for(ri i=0; i<n; ++i) a[i]=A[i],b[i]=B[i]; fwtor(a,1), fwtor(b,1); for(ri i=0; i<n; ++i) a[i]=(LL)a[i]*b[i]%md; fwtor(a,-1); } void calcand() { for(ri i=0; i<n; ++i) a[i]=A[i],b[i]=B[i]; fwtand(a,1), fwtand(b,1); for(ri i=0; i<n; ++i) a[i]=(LL)a[i]*b[i]%md; fwtand(a,-1); } void calcxor() { for(ri i=0; i<n; ++i) a[i]=A[i],b[i]=B[i]; fwtxor(a,1), fwtxor(b,1); for(ri i=0; i<n; ++i) a[i]=(LL)a[i]*b[i]%md; fwtxor(a,-1); } ``` ## FMT 高维差分前缀和 ```cpp void fmt(int a[]) { for(ri i=1; i<=U; i<<=1) for(ri j=0; j<=U; ++j) if(j&i) (a[j]+=a[j^i])%=md; } void ifmt(int a[]) { for(ri i=1; i<=U; i<<=1) for(ri j=0; j<=U; ++j) if(j&i) (a[j]-=a[j^i])%=md; } ``` --------------- ### WC2018州区划分 如何解决一类特殊的OR卷积问题：$a[s]\times b[t]\to c[s|t],s\bigcap t=0 $，也就是OR卷积但没有交集。 我们可以多记一维状态：$a,b[cnt][s]$，表示S在二进制下有cnt个1的情况。这样，我们枚举a集合的cnt，则b集合的cnt就是剩下的。然后做OR卷积即可。因为我们保证元素个数，而它们并起来的个数也是这个，所以没有交集。 ### 子集位运算 给定m个数，对$i\in [0,2^n-1]$求出子集&为i的子集数量。 先高维后缀和，然后我们要计算子集&起来至少为i的数量，就是$2^{cnt}-1$，然后高维差分即可。 ### 10进制FWT 见另一篇博客：CF772D ### 【UNR #2】黎明前的巧克力 好题！ 注意到dp式子为 $$dp[i][j]=dp[i-1][j]+dp[i-1][j\oplus a[i]]$$ 相当于FWT一个b，其中$b[0]=1,b[a[i]]=2$ 但是直接做太慢了，考虑优化。 $FWT(b)$应该全为-1或3，因为b[0]会向每个位置贡献贡献1，b[a[i]]会贡献2或-2. **FWT的和=和的FWT** 所以说，我们如果求出FWT的和，就能解出-1和3的个数，从而得知原本的FWT的乘积。 ### LOJ154 集合划分计数 见另一篇博客。