位运算卷积：
定义位运算卷积：
第 \(i\) 项和第 \(j\) 项的乘积贡献到第 \(i⊕j\) 项。其中 \(⊕\) 是某种位运算，即：
\[S[k]=\sum_{i⊕j=k}A[i]⋅B[j] \]记作：
\[S=A*B \]构造 \(FWT\) 变换：
尝试把位运算卷积转化成点积。
设 \(fwt(A)\) 是幂级数 \(A\) 经过 \(FWT\) 变换之后得到的幂级数，其满足：
\[A*B=C⟺fwt(A)⋅fwt(B)=fwt(C) \]我们希望构造出来的是一个线性变换，设：
\[fwt(A)[i]=\sum_{j=0}^{n-1}c(i,j)⋅A[j] \]有：
\[fwt(S)[i]=fwt(A)[i]⋅fwt(B)[i] \] \[\sum_{j=0}^{n-1}c(i,j)⋅S[j]=\sum_{k=0}^{n-1}c(i,k)⋅A[k]⋅\sum_{p=0}^{n-1}c(i,p)⋅B[p] \] \[\sum_{j=0}^{n-1}c(i,j)⋅S[j]=\sum_{k=0}^{n-1}\sum_{p=0}^{n-1}c(i,k)⋅c(i,p)⋅A[k]⋅B[p] \]由 \(S=A*B\) 有：
\[S[p]=\sum_{j⊕k=p}A[j]⋅B[k] \] \[\sum_{p=0}^{n-1}c(i,p)⋅S[p]=\sum_{p=0}^{n-1}c(i,p)⋅\sum_{j⊕k=p}A[j]⋅B[k] \] \[\sum_{p=0}^{n-1}c(i,p)⋅S[p]=\sum_{p=0}^{n-1}\sum_{j⊕k=p}c(i,p)⋅A[j]⋅B[k] \] \[=\sum_{p=0}^{n-1}\sum_{j⊕k=p}c(i,j⊕k)⋅A[j]⋅B[k] \] \[=\sum_{i=0}^{n-1}\sum_{k=0}^{n-1}c(i,j⊕k)⋅A[j]⋅B[k] \]由 \(\sum_{j=0}^{n-1}\limits c(i,j)⋅S[j]=\sum_{k=0}^{n-1}\limits \sum_{p=0}^{n-1}\limits c(i,k)⋅c(i,p)⋅A[k]⋅B[p]\) 得：
\[\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}c(i,j)⋅c(i,k)⋅A[j]⋅B[k]=\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}c(i,j⊕k)⋅A[j]⋅B[k] \]因此，只需有：
\[c(i,j)⋅c(i,k)=c(i,j⊕k) \]另外，由于位运算每一位的独立性，有：
\[c(i,j)=\prod_{k=0}^{log\ n}c(i_k,j_k) \]因此：
\[c(i,j)⋅c(i,k)=c(i,j⊕k)⟺c(i_t,j_t)⋅c(i_t,k_t)=c(i_t,j_t⊕k_t),\forall t\in[0,log\ n] \]因此我们只要针对不同的位运算构造出一个 \(2*2\) 的矩阵即可
1. \(Or\) 卷积
设：
\[c=\left[ \begin{matrix} {c(0,0)}&{c(0,1)}\\ {c(1,0)}&{c(1,1)}\\ \end{matrix} \right ]\]有：
\[\begin{cases} \ \ c(0,0)⋅c(0,0)=c(0,0),&c(0,0)⋅c(0,1)=c(0,1)\\ \\ \ \ c(0,1)⋅c(0,0)=c(0,1),&c(0,1)⋅c(0,1)=c(0,1)\\ \\ \ \ c(1,0)⋅c(1,0)=c(1,0),&c(1,0)⋅c(1,1)=c(1,1)\\ \\ \ \ c(1,1)⋅c(1,0)=c(1,1),&c(1,1)⋅c(1,1)=c(1,1)\\ \end{cases} \]为了方便在变换后还原，矩阵必须要有逆，因此，最终答案有两个：
\[\begin{cases} c_1=\left[ \begin{matrix} {1}&{1}\\ {1}&{0}\\ \end{matrix} \right ],&& c_2=\left[ \begin{matrix} {1}&{0}\\ {1}&{1}\\ \end{matrix} \right ] \end{cases} \]对于第二个矩阵，显然有 \(c(i,j)=[j\)&\(i=j]\) 因此我们使用第二个矩阵。
还原时对矩阵求逆即可：
\[c^T=\left[ \begin{matrix} {1}&{0}\\ {-1}&{1}\\ \end{matrix} \right ]\]2. \(And\) 卷积
设：
\[c=\left[ \begin{matrix} {c(0,0)}&{c(0,1)}\\ {c(1,0)}&{c(1,1)}\\ \end{matrix} \right ]\]有：
\[\begin{cases} \ \ c(0,0)⋅c(0,0)=c(0,0),&c(0,0)⋅c(0,1)=c(0,0)\\ \\ \ \ c(0,1)⋅c(0,0)=c(0,0),&c(0,1)⋅c(0,1)=c(0,1)\\ \\ \ \ c(1,0)⋅c(1,0)=c(1,0),&c(1,0)⋅c(1,1)=c(1,0)\\ \\ \ \ c(1,1)⋅c(1,0)=c(1,0),&c(1,1)⋅c(1,1)=c(1,1)\\ \end{cases} \]最终答案有两个：
\[\begin{cases} c_1=\left[ \begin{matrix} {0}&{1}\\ {1}&{1}\\ \end{matrix} \right ],&& c_2=\left[ \begin{matrix} {1}&{1}\\ {0}&{1}\\ \end{matrix} \right ] \end{cases} \]对于第二个矩阵，显然有 \(c(i,j)=[j\)&\(i=i]\) 因此我们使用第二个矩阵。
还原时对矩阵求逆即可：
\[c^T=\left[ \begin{matrix} {1}&{-1}\\ {0}&{1}\\ \end{matrix} \right ]\]3. \(Xor\) 卷积
设：
\[c=\left[ \begin{matrix} {c(0,0)}&{c(0,1)}\\ {c(1,0)}&{c(1,1)}\\ \end{matrix} \right ]\]有：
\[\begin{cases} \ \ c(0,0)⋅c(0,0)=c(0,0),&c(0,0)⋅c(0,1)=c(0,1)\\ \\ \ \ c(0,1)⋅c(0,0)=c(0,1),&c(0,1)⋅c(0,1)=c(0,0)\\ \\ \ \ c(1,0)⋅c(1,0)=c(1,0),&c(1,0)⋅c(1,1)=c(1,1)\\ \\ \ \ c(1,1)⋅c(1,0)=c(1,1),&c(1,1)⋅c(1,1)=c(1,0)\\ \end{cases} \]最终答案有四个：
\[\begin{cases} c_1=\left[ \begin{matrix} {1}&{1}\\ {-1}&{1}\\ \end{matrix} \right ],&& c_2=\left[ \begin{matrix} {1}&{1}\\ {1}&{-1}\\ \end{matrix} \right ],&& c_3=\left[ \begin{matrix} {-1}&{1}\\ {1}&{1}\\ \end{matrix} \right ],&& c_4=\left[ \begin{matrix} {1}&{-1}\\ {1}&{1}\\ \end{matrix} \right ] \end{cases} \]对于第二个矩阵，显然有 \(c(i,j)=(-1)^{|i\& j|}\) 因此我们使用第二个矩阵。
还原时对矩阵求逆即可：
\[c^T=\left[ \begin{matrix} {0.5}&{0.5}\\ {0.5}&{-0.5}\\ \end{matrix} \right ]\]\(FWT\) 变换的一些性质：
\(FWT\) 是线性变换：
\[\begin{cases} fwt(A+B)=fwt(A)+fwt(B)\\ \\ fwt(c⋅A)=c⋅fwt(A) \end{cases} \]由定义 \(fwt(A)[i]=\sum_{j=0}^{n-1}\limits c(i,j)⋅A[j]\) 后显然可证。
- 求：
从序列 \(\{a_i\}\) 中选择一个非空子集，使子集内的数按位与起来为零
\[\]solution 1:
令 \(dp[s]\) 表示按位与起来结果为 \(s\) 的超集的方案数
\(FWT\) 求出 \(dp[s]\) ，则有：
\[ans=\sum_{s=0}(-1)^{cnt[s]}dp[s] \]solution 2:
令 \(dp[i][s]\) 表示到了第 \(i\) 位，运算结果位 \(s\) 的方案数，有：
\[dp[i][s]=dp[i-1][s]+\sum_{s=j\&a[i]}dp[i-1][j] \] \[dp[i][s]=dp[i-1][s]+\sum_{p\&k=s}[p=a[i]]⋅dp[i-1][k] \]对上式进行 \(fmt\) 变换，由于 \(fwt(A+B)=fwt(A)+fwt(B)\) 可知：
\[fwt(dp[i-1][s]+\sum_{p\&k=s}[p=a[i]]⋅dp[i-1][k])=fwt(dp[i-1][s])+fwt(\sum_{p\&k=s}[p=a[i]]⋅dp[i-1][k]) \]显然：
\[fwt(\sum_{p\&k=s}[p=a[i]]⋅dp[i-1][k])=fwt([p=a[i]])⋅fwt(dp[i-1][p]) \]因此：
\[fwt(dp[i][s])=fwt(dp[i-1][s])*(1+fwt([p=a[i]])) \]记 \(cnt[s]=\sum_{i=1}^{n}\limits [s=a[i]]\)
\[fwt(dp[n][s])=2^{fwt(cnt[s])} \]【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)
#include<bits/stdc++.h>
using namespace std;
int n;
int A[(1<<17)+5],B[(1<<17)+5];
int a[(1<<17)+5],b[(1<<17)+5],c[(1<<17)+5];
const int md=998244353;
inline void cpy(){
for(int i=0;i<(1<<n);i++)a[i]=A[i];
for(int i=0;i<(1<<n);i++)b[i]=B[i];
}
inline void solve(){
for(int i=0;i<(1<<n);i++)c[i]=(1ll*a[i]*b[i])%md;
}
inline void output(){
for(int i=0;i<(1<<n);i++)printf("%d ",(c[i]+md)%md);
puts("");
}
inline void And(int *dp,int x){
for(int i=0;i<n;i++){
for(int s=0;s<(1<<n);s++){
if((s>>i)&1)continue;
dp[s]=(dp[s]+x*dp[s|(1<<i)])%md;
}
}
}
inline void Or(int *dp,int x){
for(int i=0;i<n;i++){
for(int s=0;s<(1<<n);s++){
if((s>>i)&1)continue;
dp[s|(1<<i)]=(dp[s|(1<<i)]+x*dp[s])%md;
}
}
}
inline void Xor(int *dp,int x){
for(int i=0;i<n;i++){
for(int s=0;s<(1<<n);s++){
if((s>>i)&1)continue;
long long u=dp[s],t=dp[s|(1<<i)];
dp[s]=1ll*x*(u+t)%md;
dp[s|(1<<i)]=1ll*x*(u-t)%md;
}
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<(1<<n);i++)scanf("%d",&A[i]);
for(int i=0;i<(1<<n);i++)scanf("%d",&B[i]);
cpy();Or(a,1);Or(b,1);solve();Or(c,-1);output();
cpy();And(a,1);And(b,1);solve();And(c,-1);output();
cpy();Xor(a,1);Xor(b,1);solve();Xor(c,(md+1)>>1);output();
return 0;
}
Jzzhu and Numbers
code 1:
#include<bits/stdc++.h>
using namespace std;
int n;
int dp[1<<20],f[1<<20],cnt[1<<20];
const int md=1e9+7;
inline int pwr(int x,int y){
int res=1;
while(y){
if(y&1)res=1ll*res*x%md;
x=1ll*x*x%md;y>>=1;
}return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
dp[x]++;
}
for(int i=0;i<20;i++){
for(int s=0;s<(1<<20);s++){
if((s>>i)&1)continue;
dp[s]+=dp[s|(1<<i)];
}
}
for(int i=0;i<(1<<20);i++)f[i]=pwr(2,dp[i])-1;
long long ans=0;
for(int i=0;i<(1<<20);i++){
cnt[i]=cnt[i>>1]+(i&1);
if(cnt[i]&1)ans=(ans-f[i])%md;
else ans=(ans+f[i])%md;
}
printf("%lld",(ans+md)%md);
return 0;
}
code 2:
#include<bits/stdc++.h>
using namespace std;
int n;
int dp[1<<20],f[1<<20],cnt[1<<20];
const int md=1e9+7;
inline int pwr(int x,int y){
int res=1;
while(y){
if(y&1)res=1ll*res*x%md;
x=1ll*x*x%md;y>>=1;
}return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
dp[x]++;
}
for(int i=0;i<20;i++){
for(int s=0;s<(1<<20);s++){
if((s>>i)&1)continue;
dp[s]+=dp[s|(1<<i)];
}
}
for(int i=0;i<(1<<20);i++)dp[i]=pwr(2,dp[i]);
for(int i=0;i<20;i++){
for(int s=0;s<(1<<20);s++){
if((s>>i)&1)continue;
dp[s]=(dp[s]-dp[s|(1<<i)])%md;
}
}
printf("%d",(dp[0]+md)%md);
return 0;
}