集合幂级数
thy21171
·
·
算法·理论
读前提醒：本篇文章着重讲的是大体思路，具体细节可能会有所略过。
集合幂级数
定义 f(x)=\sum\limits_Sf_Sx^S 为集合幂级数。它的乘法形如 x^S\times x^T=\begin{cases}x^{S\cup T}&S\cap T=\emptyset\\0&\texttt{otherwise}\end{cases}。
集合并乘法
也就是熟悉的 fwt 或卷积。
补：我们把集合幂级数的集合并乘法写作：$f=a*b$。
## 乘法
也就是熟悉的子集卷积。
算的是：$f_S=\sum\limits_{u\cap v=\phi,u\cup v=S}a_ub_v$，又写作 $f=a\times b$。
用集合幂级数的方式写出来：
$$f(x)=(\sum_Sa_Sx^S)(\sum_Tb_Tx^T)$$
这个时候发现了一个问题，如果用或卷积，对于每个 $S$ 我们会多算 $u\cap v\neq\phi,u\cup v=S$ 的 $(u,v)$ 的贡献。
考虑这样一个恒等式 $|u|+|v|\ge|u\cup v|$。发现如果这个式子取等，那么说明这一对 $(u,v)$ 可以算入贡献。
考虑爆改集合幂级数的式子，多加一个未知数（占位）$y$，定义它的乘法为正常的多项式乘法（$y^a\times y^b=y^{a+b}$）。
考虑将 $a_S$ 的集合幂级数写成 $\sum\limits_Sa_Sx^Sy^{|S|}$，$b$ 同理。
这时候 $f(x,y)=(\sum\limits_Sa_Sx^Sy^{|S|})(\sum\limits_Tb_Tx^Ty^{|T|})$。
对这个式子直接做集合并乘法，得到的 $f(x,y)$ 形如 $\sum\limits_{S,i}f_{S,i}x^Sy^i$。只有当 $|S|=i$ 时这组 $(S,i)$ 才有贡献，模拟这个过程即可。
我们还可以发现，这个东西可以这个东西可以按 $y$ 的次数从小到大做（即按 $|S|$ 从小到大），时间复杂度一样。这个东西就叫半在线卷积，后面的全家桶都有用到。
## inv
对于 $(\sum\limits_Sa_Sx^S)(\sum\limits_Tf_Tx^T)=1$ 求 $f$。
首先有 $f_0=\frac1{a_0}$。
将式子变形：
$$f_S=\frac{1-\sum_{T\sub S}f_Ta_{S-T}}{a_0}$$
用半在线卷积维护即可。
## exp
这里记录两种方法，一种需要逆元；一种不需要逆元，但是由于要魔改 fwt 导致某些题无法卡常。
先讲第一种：
首先有 $f(x,y)=e^{a(x,y)}$，以 $y$ 为主元求导后有 $f'=a'f$，将其展开：
$$\sum_{S,i}(i+1)f_{i+1,S}x^Sy^i=(\sum_{S,i}(i+1)a_{i+1,S}x^Sy^i)(\sum_{T,j}f_{j,T}x^Sy^j)$$
取 $y^i$ 的系数（注意这里有子集卷积）：
$$[x^S](i+1)f_{i+1}=[x^S]\sum_{j=0}^i(j+1)a_{j+1}\times f_{i-j}$$
整理得：
$$f_i=\frac 1i\sum_{j=1}^ija_jf_{i-j}$$
讲讲第二种：
设 $f=e^a$，泰勒展开后考虑其组合意义。
若 $[x^S]a$ 代表的是 $S$ 这个集合的权值，则 $[x^S]f$ 代表的就是无序将 $S$ 划分成若干集合，这些集合的权值乘积之和。
考虑 $dp$。由于是无序，考虑钦定枚举的顺序。
$$f_S=a_S+\sum\limits_{T\subset S,\min(T)=\min(S)}a_Tf_{S-T},\min(S)=\min\limits_{x\in S}x$$
用半在线卷积维护这个式子。
这里由于固定了最小值，还要魔改一下 fwt。
## ln
同样有两种方法。
第一种：
类似地，首先有 $a(x,y)=e^{f(x,y)}$，以 $y$ 为主元求导后有 $a'=f'a$，将其展开：
$$\sum_{S,i}(i+1)a_{i+1,S}x^Sy^i=(\sum_{S,i}(i+1)f_{i+1,S}x^Sy^i)(\sum_{T,j}a_{j,T}x^Sy^j)$$
取 $y^i$ 的系数（注意这里有子集卷积）：
$$[x^S](i+1)a_{i+1}=[x^S]\sum_{j=0}^i(j+1)f_{j+1}\times a_{i-j}$$
整理得：
$$a_i=\frac 1i\sum_{j=1}^ijf_ja_{i-j}$$
由于 $a_0=1$：
$$if_i=ia_i-\sum_{j=1}^{i-1}jf_ja_{i-j}\\f_i=a_i-\frac{\sum_{j=1}^{i-1}jf_ja_{i-j}}i$$
第二种：
考虑将 exp 的组合意义反过来。
$$f_S=a_S-\sum\limits_{T\subset S,\min(T)=\min(S)}f_Ta_{S-T}$$
# 应用
## 连通块限制
### [P11734](https://www.luogu.com.cn/problem/P11734)
exp 组合意义的应用。
设 $f_S$ 为点集为 $S$ 的导出子图是联通的方案数，发现 $[x^S]g=[x^S]e^f$ 代表的恰好是点集 $S$ 导出子图的方案数（去掉了联通的限制）。
后者可以轻易的求出，$g_S=2^{cnt_S}$，其中 $cnt_S$ 代表点集 $S$ 的导出子图有多少条边。然后通过 $f=\ln g$ 求出 $f$。
最后答案：
$$ans=\sum_i\frac{f^i}{i!}i!=\frac1{1-f}$$
### [ARC105F](https://www.luogu.com.cn/problem/AT_arc105_f)
要数无向图联通二分子图的数量设 $S\to T$ 的边的数量有 $e_{S,T}$ 条，显然有 $e_{S,T}=cnt_{S\cup T}-cnt_S-cnt_T$。
设 $f_S$ 表示点集为 $S$ 的二分子图的数量，$g_S$ 表示点集为 $S$ 的联通二分子图的数量。
$$f_S=\sum\limits_{T\subseteq S}2^{e_{T,S-T}},g=\ln f$$
但是发现 $f$ 有点问题，如果有 $k$ 个联通块，这种情况会被算 $2^k$ 次。相当于一个联通块的权值为 $2$，所有最后答案除以二就是正确答案。
## 数 DAG
### [P6846](https://www.luogu.com.cn/problem/P6846)
要数 DAG 的数量，考虑每次删去入度为 $0$ 的点集。设 $f_S$ 为点集为 $S$ 的 DAG 数量，$w_S$ 表示 $S$ 是否是独立集。
$$f_S=\sum_{T\subseteq S,T
\neq\emptyset}w_Tf_{S-T}$$
这样会算重，尝试配凑容斥系数。
我们希望 $\sum\limits_{T\subseteq S,T\neq\emptyset}g(T)=1$，解得 $g(S)=(-1)^{|S|-1}$。
于是正确的转移方程为：
$$f_S=\sum_{T\subseteq S,T
\neq\emptyset}(-1)^{|T|-1}w_Tf_{S-T}$$
这种方法称为 DAG 容斥。
### [P11714](https://www.luogu.com.cn/problem/P11714)
要数强连通图的方案数。
[这篇题解](https://www.luogu.com.cn/article/s9xcssc8)已经足够优秀了。
---
主要参考：[集合幂级数在子图计数问题上的应用](https://molmin.github.io/image/2025/05/15/ji-he-mi-ji-shu-zai-zi-tu-ji-shu-wen-ti-shang-de-ying-yong-chen-xin-yang.pdf)。