参考资料：集合幂级数相关 by Alex_Wei
集合幂级数
定义
定义集合 \(U=\{1,2,\cdots,n\}\)，\(2^U\) 表示 \(U\) 的所有子集构成的集合。
定义从集合到数值的映射 \(f\)，则集合幂级数 \(f=\sum_{S\in 2^{U}} f_{S}x^S\)，\(x^S\) 只是占位符，用来表示 \(S\) 对应位置，并无实际意义。
运算
加法运算同正常形式幂级数相同，对应位置加和即可。
乘法运算的系数仍然是对应相乘，而下标的运算则是按照一种关于集合的运算 \(\oplus\)。
\[h=f\cdot g=\sum_{L\in 2^U}f_Lx^L\cdot\sum_{R\in 2^U}g_Rx^R \]对于某一项而言：
\[h_S=\sum_{L,R\in 2^U}[L\oplus R=S]f_Lg_R \]于是整体：
\[h=\sum_{S\in 2^U}\sum_{L,R\in 2^U}[L\oplus R=S]a_Lb_R x^S \]应用
多数情况下我们将状态压成二进制并卷积进行计算，因此应用较广的是以位运算作为 \(\oplus\)，也称为 位运算卷积。
子集相关运算
高位前（后）缀和
\[f(S)=\sum_{T\subseteq S} g(T) \]\[f(S)=\sum_{S\subseteq T}g(T) \]对于第一个式子，枚举当前位置 \(k\)，假设已知前 \(k-1\) 位的和，即 \(f(S)\) 得到的贡献 \(g(T)\) 中 \(T\) 在前 \(k-1\) 位是 \(S\) 的子集，剩余位置与 \(S\) 相同，计算第 \(k\) 位实际上是这一位是 \(0\) 的答案贡献到是 \(1\) 的位置。
而第二个式子则是 \(1\) 到 \(0\) 的贡献。
点击查看代码
//前缀
for(int k=0;k<n;++k){
for(int i=0;i<(1<<n);++i){
if(i&(1<<k)) f[i]+=f[i^(1<<k)];
}
}
//后缀
for(int k=0;k<n;++k){
for(int i=0;i<(1<<n);++i){
if(!(i&(1<<k))) f[i]+=f[i^(1<<k)];
}
}
高维前（后）缀差分
子集和超集反演之后，得到：
\[g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|} f(T) \]\[g(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|} f(T) \]只需要在转移时增加一个系数 \(-1\)，至于没有次数的原因，考虑 \(T\) 到 \(S\) 的靠拢过程应当是增补 \(1\)（作为子集）或削去 \(1\)（作为超集），这样转移次数就是两个集合大小之差，每次转移乘 \(-1\)，正符合上面式子的次数。
点击查看代码
//前缀
for(int k=0;k<n;++k){
for(int i=0;i<(1<<n);++i){
if(i&(1<<k)) f[i]-=f[i^(1<<k)];
}
}
//后缀
for(int k=0;k<n;++k){
for(int i=0;i<(1<<n);++i){
if(!(i&(1<<k))) f[i]-=f[i^(1<<k)];
}
}
快速莫比乌斯变换 \(\text{FMT(Fsat Mobius Transform)}\)
或卷积（集合并卷积）
考虑构造 \(f'_S=\sum_{T\subseteq S}f_T\)，则 \(f_S=\sum_{T\subseteq S}(-1)^{|S|-|T|}f'_T\)。
\[\begin{aligned} h’_S&=\sum_{T\subseteq S}\sum_{L\in 2^U,R\in 2^U}[L\cup R=T] f_Lg_R\\ &=\sum_{L\in 2^U,R\in 2^U}[L\cup R\subseteq S] f_Lg_R\\ &=\sum_{L\in 2^U,R\in 2^U}[L\subseteq S][R\subseteq T] f_Lg_R\\ &=\sum_{L\in 2^U} [L\subseteq S] f_L\sum_{R\in 2^U} [R\subseteq S] g_R\\ &=f'_Lg'_R \end{aligned}\]于是做法是先构造出 \(f'\) 与 \(g'\)，乘出 \(h'\)，再逆变换回 \(h\)，这个逆变换称为 \(\text{FMI(Fsat Mobius Inversion)}\)。
与卷积（集合交卷积）
考虑构造 \(f'_S=\sum_{S\subseteq T}f_T\)，则 \(f_S\sum_{S\subseteq T}(-1)^{|S|-|T|}f'_T\)。
把或卷积稍微改变一下。
\[\begin{aligned} h’_S&=\sum_{S\subseteq T}\sum_{L\in 2^U,R\in 2^U}[L\cap R=T] f_Lg_R\\ &=\sum_{L\in 2^U,R\in 2^U}[S\subseteq L\cap R] f_Lg_R\\ &=\sum_{L\in 2^U,R\in 2^U}[S\subseteq L][S\subseteq R] f_Lg_R\\ &=\sum_{L\in 2^U} [S\subseteq L] f_L\sum_{R\in 2^U} [S\subseteq R] g_R\\ &=f'_Lg'_R \end{aligned}\]点击查看代码
int n;
inline void FMT_or(int *f,int c){
for(int k=0;k<n;++k){
for(int i=0;i<(1<<n);++i){
if(i&(1<<k)) f[i]=(f[i]+1ll*c*f[i^(1<<k)]%mod)%mod;
}
}
}
inline void FMT_and(int *f,int c){
for(int k=0;k<n;++k){
for(int i=0;i<(1<<n);++i){
if(!(i&(1<<k))) f[i]=(f[i]+1ll*c*f[i^(1<<k)]%mod)%mod;
}
}
}
int a[maxn],b[maxn];
int F[maxn],G[maxn],H[maxn];
int main(){
n=read();
for(int i=0;i<(1<<n);++i) a[i]=read();
for(int i=0;i<(1<<n);++i) b[i]=read();
for(int i=0;i<(1<<n);++i) F[i]=a[i],G[i]=b[i];
FMT_or(F,1),FMT_or(G,1);
for(int i=0;i<(1<<n);++i) H[i]=1ll*F[i]*G[i]%mod;
FMT_or(H,mod-1);
for(int i=0;i<(1<<n);++i) printf("%d ",H[i]);
printf("\n");
for(int i=0;i<(1<<n);++i) F[i]=a[i],G[i]=b[i];
FMT_and(F,1),FMT_and(G,1);
for(int i=0;i<(1<<n);++i) H[i]=1ll*F[i]*G[i]%mod;
FMT_and(H,mod-1);
for(int i=0;i<(1<<n);++i) printf("%d ",H[i]);
printf("\n");
return 0;
}
特殊性质
注意到与多项式乘法中的 \(\text{FFT}\) 不同的是，\(\text{FMT}\) 是一个纯粹的线性求和，因此经过若干次运算后规模仍然是 \(2^U\)。
这使得我们在进行多次乘法时，可以全部 \(\text{FMT}\) 后求积再 \(\text{FMI}\)，而不必要像 \(\text{FFT}\) 一样每次都在系数与点值之间来回切换。