集合幂级数——学习笔记

学习自 \(VFK\)\(2015\) 集训队论文。

数学上没有集合幂级数这个名称,这应该是类比多项式那套理论取的名字。

集合幂级数的表示: \[ f=\sum_{S\in2^{U}} f_Sx^S \] 注意这个 \(x^S\) 只是一个符号。

集合幂级数的乘法: \[ h=f \cdot g \\ \sum_{S \in 2^U} h_S=\sum_{L\in2^U} \sum_{R\in2^U}[L*R=S]f_Lg_R \] \(L*R\) 即是某种关于集合的运算。

集合并卷积

\(L*R=L\cup R\) 。快速求卷积需要快速莫比乌斯变换:

很经典的容斥。 \[ \hat f_S =\sum_{T \subseteq S} f_T \\ f_S=\sum_{T \subseteq S} (-1)^{|S|-|T|} \hat f_T \]

可以快速做变换:

1
2
3
4
5
6
7
8
9
10
void FMT(int a[],int n,int K){
for(int i=0;i<=(1<<n)-1;i<<=1)
for(int j=0;j<=(1<<n)-1;j++)
if(i&j) f[i]+=f[i^j];
}
void iFMT(int a[],int n,int K){
for(int i=0;i<=(1<<n)-1;i<<=1)
for(int j=0;j<=(1<<n)-1;j++)
if(i&j) f[i]-=f[i^j];
}

对于集合并卷积,有 \(\hat{h}_S=\hat{f}_S \hat{g}_S\) 。这样就可以 \(O(n2^n)\) 求了。

其实直接 \(FWT\) 就行了。

对称差卷积

即异或卷积, 就 \(FWT\)

子集卷积

\(L*R\) 必须满足交为空,然后 \(L*R=L \cup R\)

相当于多了一个 \(|L|+|R|=|L\cup R|\) 的限制。这时需要多一维表示集合大小,然后可以转化为子集并。

复杂度 \(O(n^2 2^n)\) ,代码长这样:

1
2
3
4
5
6
7
8
9
for(int i=0;i<=n;i++) FMT(f[i]), FMT(g[i]);
for(int i=1;i<=n;i++){
for(int j=0;j<=i;j++)
for (int k=0;k<=(1<<n)-1;k++)
(h[i][k]+=(LL)f[j][k]*g[i-j][k]%P)%=P;
iFMT(h[i]);
for(int k=0;k<=(1<<n)-1;k++) if(cnt[k]!=i) h[i][k]=0;
if (i!=n) FMT(h[i]);
}