集合幂级数与子图计数

集合幂级数概论

集合幂级数

定义

设全集 $U=\{1,2,\cdots,n\},\mathbf{U}=\{S\mid S\subseteq U\}$。定义 $U$ 上的集合幂级数 $f:\mathbf{U}\to R$，其中 $R$ 为一交换环。令 $f_S$ 表示 $f$ 上 $S$ 的像。

若 $f:\mathbf{U}\to R,g:\mathbf{U}\to R$，则定义：

• $h=f+g$，其中 $h:\mathbf{U}\to R$ 且 $h_S=f_S+g_S$。类似的可以定义 $h=f-g$。
• $h=kf$，其中 $h:\mathbf{U}\to R,k\in R$，其中 $h_S=kf_S$，类似的可以定义 $h=-f$。
• $h=f\times g$，其中 $h:\mathbf{U}\to R$ 且 $h_S=\sum\limits_{T\subseteq S} f_Tg_{S\backslash T}$，即 $f,g$ 的子集卷积（不交并卷积）。
  为了方便之后的表述，我们定义 $S\sqcup T$ 表示 $S,T$ 的不交并（若 $S\cap T=\varnothing$，则 $S\sqcup T=S\cup T$，否则是非法的）。
• $h=f\ast g$，其中 $h:\mathbf{U}\to R$ 且 $h_S=\sum\limits_{A\cup B=S} f_Ag_B$，即 $f,g$ 的集合并卷积（OR 卷积）。
• $h=f\circ g$，其中 $h:\mathbf{U}\to R$ 且 $h_S=f_S\cdot g_S$，即 $f,g$ 的逐项积。

另外还可以定义集合交卷积（AND 卷积）、集合对称差卷积（XOR 卷积）等，它们在一般的 FMT/FWT 技术中是十分重要的，不过它们在集合幂级数理论中应用较少，故不再赘述。

若令 $U=\{1,2,\cdots,n\}$ 上的全体集合幂级数集合为 $\mathbf{F}(U,R)$，则可以验证代数结构 $(\mathbf{F}(U,R),+,\times)$ 是一个交换环，并是一个自由模。

我们可以取自由模的一组基，共有 $2^n$ 个基向量。因此可以构建一个 $U$ 的子集到基向量的映射 $f:U\to \mathbf{F}(U,R)$ 其中 $f_{S,T}=[S=T]$，也就是 one-hot 的集合幂级数，并将这样的集合幂级数 $f_S$ 记作 $z^S$，其中 $z$ 是占位元，不代表实际的数。

根据基的性质，我们可以将任意一个 $\mathbf{F}(U,R)$ 中的集合幂级数表示为若干个基的数乘之和的形式，即：

$$f = \sum_{S\subseteq U} f_S z^S$$

仿照级数的，我们也可以定义集合幂级数的取系数算子 $[z^S]f = f_S$，如果 $R$ 是一个多项式环，还可以组合级数的取系数算子使用，如 $[z^Sx^k]f=[x^k]f_S$。

这样我们就成功定义了集合幂级数以及其相关的运算（线性运算、卷积运算），并且让它具有类似一般地级数的形式。

快速莫比乌斯变换

快速莫比乌斯变换用于快速计算集合 OR 卷积。

定义

对于 $\mathbf{F}(U,R)$ 中的集合幂级数 $f$，定义其莫比乌斯变换（Moebius Transform） $\textsf{FMT}(f)$ 为：

$$\textsf{FMT}(f)=\sum_{S\subseteq U}z^S\sum_{T\subseteq S}f_T$$

即 $f$ 的子集和。

定义 $f$ 的莫比乌斯逆变换 $\textsf{IFMT}(f)$ 满足 $\textsf{FMT}(\textsf{IFMT})=f$。

我们将给出一个引理，证明莫比乌斯变换可以帮助我们计算 OR 卷积：

引理

对于 $\mathbf{F}(U,R)$ 中的集合幂级数 $f,g$，有：

$$\textsf{FMT}(f\ast g) = \textsf{FMT}(f) \circ \textsf{FMT}(g)$$

证明这个引理也不难，只需要按照各部分定义变形即可：

$$\begin{aligned} \textsf{FMT}(f) \circ \textsf{FMT}(g)&=\sum_{S\subseteq U} \left(\sum_{T\subseteq S} f_T\right) \left(\sum_{T\subseteq S} g_T\right) z^S = \sum_{S\subseteq U} z^S \sum_{A\subseteq S, B\subseteq S} f_A g_B \\ &= \sum_{S\subseteq U} z^S \sum_{T\subseteq S} \sum_{A\cup B=T} f_A g_B = \textsf{FMT}(f\ast g) \end{aligned}$$

根据该定理，我们得到了一个快速求 OR 卷积的方法：先将 $f,g$ 进行莫比乌斯变换 $\textsf{FMT}(f),\textsf{FMT}(g)$，然后计算这两个集合幂级数的逐项乘积 $h=f\circ g$，最后 $\textsf{IFMT}(h)$ 即为 $f\ast g$ 的值。

那么现在我们需要快速进行莫比乌斯变换以及其逆变换。注意到这个莫比乌斯变换的形式和高维前缀和一模一样，莫比乌斯逆变换对应高维差分，因此可以使用高维前缀和的标准方法：Sum over Subsets DP 来做。

Sum over Subsets DP 求高维前缀和

直接给出一个代码吧，这个东西挺简单的：

void fmt(int *a, int n){
    for(int i=1;i<=n;i++){
        for(int j=0;j<(1<<n);j++){
            if((j >> (i - 1)) & 1) a[j] = Add(a[j], a[j ^ (1 << (i - 1))]);
        }
    }
}

void ifmt(int *a, int n){
    for(int i=1;i<=n;i++){
        for(int j=(1<<n)-1;~j;j--){
            if((j >> (i - 1)) & 1) a[j] = Sub(a[j], a[j ^ (1 << (i - 1))]);
        }
    }
}

由于 Sum over Subsets DP 可以用于快速进行莫比乌斯变换，所以又称为快速莫比乌斯变换（Fast Moebius Transform, FMT）。

另外莫比乌斯变换还有一个重要性质：

引理

对于 $\mathbf{F}(U,R)$ 中的集合幂级数 $f,g$，有：

$$\begin{aligned} &\textsf{FMT}(f + g) = \textsf{FMT}(f) + \textsf{FMT}(g)\\ &\forall k\in R, k\textsf{FMT}(f) = \textsf{FMT}(kf) \end{aligned}$$

即莫比乌斯变换是线性的。

这两条性质都是显然的，其原因是 $R$ 中的乘法分配律与加法交换律。

OR 卷积的参考实现。

占位多项式与子集卷积

首先我们需要知道一个经典推论：

推论

$$z^S\times z^T=\begin{cases} z^{S\cup T}& S\cap T=\varnothing\\ 0& \text{otherwise} \end{cases}$$

这个推论可以清晰的描述集合幂级数的子集卷积。

考虑集合的不交并运算，$S \sqcup T$ 可以看成 $S\cup T$，不过要求 $|S\cup T|=|S|+|T|$。因此可以考虑在集合幂级数中体现集合的大小信息。而集合大小是加性的，非常适合用形式幂级数描述。

定义

$\mathbf{F}(U,R)$ 中的集合幂级数 $f$ 的占位多项式为 $\overline{f}\in\mathbf{F}(U,R[x])$。其中 $R[x]$ 表示 $R$ 为系数，$x$ 为占位元的多项式环，同时 $\overline{f}_S = f_S x^{|S|}$。

然后我们将证明一个定理：

定理

对于 $\mathbf{F}(U,R)$ 中的集合幂级数 $f,g$，有：

$$(f\times g)_S = [z^S x^{|S|}](\overline{f} \ast \overline{g})$$

证明如下：

$$\begin{aligned} &\overline{f} \ast \overline{g}=\sum_{S\subseteq U} z^S \sum_{A\cup B=S} f_A g_B x^{|A|+|B|}\\ &\implies [z^S x^{|S|}](\overline{f} \ast \overline{g})=\sum_{S\subseteq U} \sum_{A\cup B=S, A\cap B=\varnothing} f_A g_B = \sum_{S\subseteq U}\sum_{T\subseteq S} f_T g_{S\backslash T} = (f\times g)_S \end{aligned}$$

因此我们只需要将占位多项式按照 OR 卷积的方法进行运算，最后的结果 $h$ 中的 $[z^{S}x^{|S|}]h$ 就是子集卷积中 $S$ 对应的结果。

FMT / IFMT 操作只涉及到了元素的加法，多项式加法时间复杂度 $O(n)$。而计算逐项乘法则需要多项式卷积，这一步时间复杂度为 $O(n^2)$ 或 $O(n\log n)$（FFT / NTT），不过在集合幂级数计算中，$n$ 往往较小（$\leq 20$），因此采用 $O(n^2)$ 的暴力常数更好、跑的更快。

最终我们得到了一个 $O(2^n \mathrm{PolyMul}(n))$ 的算法，其中 $\mathrm{PolyMul}(n)$ 一般取 $O(n^2)$。

集合幂级数的多项式复合

定义

对于多项式 $g(x)$ 与 $\mathbf{F}(U,R)$ 中的集合幂级数 $f$，其中 $|U|=n$。$f,g$ 的复合 $g(f)$ 定义为：

$$g(f)=\sum_{i=0}^{n} [x^i]g(x)\cdot f^i$$

其中 $f^i=\underbrace{f\times f\times \cdots \times f}_{i}$。

考虑如何计算复合。尝试取结果的莫比乌斯变换，然后应用 FMT 的线性性：

警告：此段内容缺失

经检验这一段内容出现了许多重大错误，因此已经删除，会在随后完善。

因此我们可以设计一个计算集合幂级数多项式复合的算法：

1. 取集合幂级数 $f$ 的占位多项式 $\overline{f}$ 的莫比乌斯变换 $h=\textsf{FMT}(\overline{f})$。
2. 对于每一个 $h_S$，计算 $h_S'=g(h_S)$，即一个多项式复合。
3. 令 $h_S\gets [x^{|S|}]{\textsf{IFMT}(h')}_{S}$ 即为所求。

注意到复杂度瓶颈在于多项式复合。朴素的 $O(n^3)$ 一般已经可以接受。虽然有 Min_25 的 $O(n\log^2 n)$ 快速算法，但是常数过大且实现极其复杂，一般不用于计算集合幂级数的多项式复合。

时间复杂度 $O(2^n\mathrm{PolyCompose}(n))$，一般取 $\mathrm{PolyCompose}(n)=O(n^3)$。

集合幂级数的逆 / exp / ln

在上节我们注意到我们有 $O(2^nn^3)$ 的一般集合幂级数多项式复合的算法，在这一节我们讨论特殊的集合幂级数复合问题。

对于一般的多项式，求逆、$\exp,\ln$ 都有 $O(n^2)$ 的朴素算法和 $O(n\log n)$ 的快速算法（基于 FFT / NTT 和牛顿迭代）。

由于求逆、$\exp$ 和 $\ln$ 都可以看成特殊的多项式复合，因此也可以采用上述的步骤，对集合幂级数求 $\exp, \ln$ 和逆，时间复杂度为 $O(2^nn^2)$。

另外生成函数有所谓【$\exp$ 的组合意义】，指的是有标号元素构成的集合来生成集族，那么集合幂级数也可以拥有 $\exp$ 的组合意义，即将一个集合划分为多个子集，求每一个子集的权值的乘积之和。这也是很容易理解的。

EI 的快速复合算法

提示

这一部分内容对于学习集合幂级数是不必要的，但是在解决一些特殊问题上需要用到。初学集合幂级数建议跳过本节。

EntropyIncreaser 的 那篇著名的博客 提出了一种复合的快速算法。无论多项式的形式，计算复合的时间复杂度始终为 $O(2^n n^2)$。

首先我们给出集合幂级数的另一个实用的表示方法：

定义

对于 $\mathbf{F}(U,R)$ 上的集合幂级数 $f$（其中 $U=\{1,2,\cdots,n\}$）。我们称环 $\mathbf{R}(U,R)=R[\![x_1,x_2,\cdots,x_n]\!]/(x_1^2,x_2^2,\cdots,x_n^2)$ 为集合幂级数的多元多项式表示环（简称多元环）。

建立映射 $G:\mathbf{F}(U,R)\to \mathbf{R}(U,R)$，且满足 $G\left(\sum_{S\subseteq U} a_Sz^S\right)=\sum_{S\subseteq U}a_S\prod_{a\in S} x^a$。

可以验证该映射为双射、满射和一一映射。并且新的表示法继承了原本集合幂级数的线性运算和乘法（子集卷积）。

考虑到抽象代数符号有点多可能影响阅读，这里给出一点解释：

• $R[\![x_1,x_2,\cdots,x_n]\!]$ 表示 $R$ 上的 $x_1,x_2,\cdots,x_n$ 幂级数环。
• $(x_1^2,x_2^2,\cdots,x_n^2)$ 为一个理想，这个理想为所有占位元的平方的线性组合。
• 因此 $\mathbf{R}(U,R)=R[\![x_1,x_2,\cdots,x_n]\!]/(x_1^2,x_2^2,\cdots,x_n^2)$ 就是一个商环，表示所有占位元的次数都不超过 $1$。

我们有一个形式幂级数 $g$ 和一个集合幂级数 $f$，我们希望计算 $g(f)$。

不妨取 $g(f)$ 的导数，那么有：

$$\frac{\partial}{\partial x_n} g(f) = g'(f) \cdot \frac{\partial}{\partial x_n} f$$

注意到集合幂级数中单个元不存在二次，那么就可以改写：

$$[x_1^n] g(f) = g'(f)\cdot [x_1^n] f$$

为了方便，不妨先假定 $g$ 是一个 EGF，并且常数项为 $0$。那么可以枚举一个元，每次使用该方程，相当于计算了一次不定积分。那么我们只需要先求出 $g(f)$ 的 $n$ 阶导数（就是 $f_n$），就可以通过迭代的方法计算出 $g(f)$ 的真实值。

类似这样：

template<class ItA, class ItB, class ItC>
void sps_in_egf(int n, ItA f, ItB g, ItC o){
    static int tmp[N_];
    *o = f[n];
    for(int i=0;i<n;i++){
        tmp[0] = *(f + n - i - 1);
        for(int j=0;j<=i;j++) subset_conv(j, o, g + (1 << j), tmp + (1 << j));
        for(int j=0;j<(2<<i);j++) *(o + j) = tmp[j];
    }
}

然后我们需要处理 $f$ 不满足我们既定条件的情况。如果 $f_0=0$，那么只需要给每一项乘上一个阶乘。如果 $f_0\neq 0$ 呢？只需要将 $f$ 平移到 $f(x+g_0)$，这样就不需要 $g_0$ 了，可以设为 $0$。

类似这样：

template<class ItA, class ItB, class ItC>
void sps_in_poly(int m, int n, ItA f, ItB g, ItC o){
    static int F[N], bin[N], pw[M_];
    if(*g != 0){
        fill(bin, bin + n + 1, 0), fill(F, F + n + 1, 0);
        bin[0] = pw[0] = 1;
        for(int i=1;i<=m;i++) pw[i] = M(pw[i - 1], *g);
        for(int i=0;i<=m;i++){
            for(int j=0;j<=min(n,i);j++) F[j] = A(F[j], M(*(f + i), M(bin[j], pw[i - j])));
            for(int j=min(n,i+1);j;j--) bin[j] = A(bin[j], bin[j - 1]);
        }
    }
    else for(int i=0;i<=min(n,m);i++) F[i] = *(f + i);
    for(int i=1,fact=1;i<=n;fact=M(fact,++i)) F[i] = M(F[i], fact);
    sps_in_egf(n, F, g, o);
}

这一算法的时间复杂度为 $O(2^n n^2)$。

子图计数

约定 $\omega(S)$ 表示原图中点 $S$ 的导出子图边数，即 $\omega(S)=\sum\limits_{(u,v)\in G} [u\in S\land v\in S]$。

约定 $\omega(S\to T)$ 表示有向图中起点位于集合 $S$，终点位于集合 $T$ 的边数，即 $\omega(S\to T)=\sum\limits_{(u,v)\in G} [u\in S\land v\in T]$。

PS：许多子图计数题的题面是不严谨的，一定要注意出题人让我们求的是 点集为 $S$ 的满足限制的子图的数量（生成子图） 还是 任意满足限制的子图的数量，大多数题目是前者（但是题面往往错写为后者，真是一笔糊涂账）。

连通性限制

连通子图计数

给定一个 $n$ 个点的无向图，求其连通子图的数量。$1\leq n\leq 20$。

考虑 $\exp$ 的组合意义，任意子图是由若干个连通子图（连通块）组成的。若定义集合幂级数 $f,g$，$f_S$ 为点集为 $S$ 的连通子图数量，$g_S$ 为点集为 $S$ 的子图数量。那么有 $g=\exp f$，即 $f=\ln g$。

又因为 $g_S=2^{\omega(S)}$ 是容易求得的，所以 $f$ 可以用集合幂级数的 $\ln$ 求。时间复杂度 $O(2^n n^2)$。

模板题：ABC213G Connectivity 2 | 提交记录。

PS：这道模板题的题意是【（对于每一个 $i\in [2, n]$，计算 $1,i$ 位于同一个连通块的生成子图数量）】，我们只需要枚举这个连通块的点集，就可以转换成连通子图计数（点集导出连通子图数量）。

二分子图计数

给定一个 $n$ 个点的无向图，求其二分子图的数量。$1\leq n\leq 20$。

有一个比较 naive 的计算方法，设 $g'_S$ 表示点集为 $S$ 的导出子图的二分子图数量，则：

$$g'_S=\sum_{P\cup Q\subseteq S, P\cap Q=\varnothing} 2^{\omega(S)-\omega(P)-\omega(Q)}$$

$\omega(S)-\omega(P)-\omega(Q)$ 的含义是点集 $S$ 的导出子图中，一端点在 $P$，另一端点在 $Q$ 的边数。

这个方法错在哪里呢？错在一个二分图的染色方案不是唯一的，一个连通二分图有两种对称的染色方案，那么一个有 $c$ 个连通块的二分图就有 $2^c$ 个染色方案。因此上述的式子其实计算到是每个二分子图的 $2^c$ 倍之和。

由于二分图是由若干个连通二分图组成的，所以根据 $\exp$ 的组合意义，若设 $f'_S$ 为表示集为 $S$ 的导出子图的连通二分子图数量的两倍，那么就有 $g'=\exp f'$，即 $f'=\ln g'$。

取 $f=\frac{1}{2}f'$，则 $f_S$ 表示点集为 $S$ 的导出子图的连通二分子图数量，那么取 $g=\exp f$ 可以得到正确的二分子图的集合幂级数。

通过 $g'$ 求出 $f'$ 的时间复杂度为 $O(2^n n^2)$，通过 $f'$ 求出 $f$ 的时间复杂度为 $O(2^n)$，通过 $f$ 求出 $g$ 的时间复杂度为 $O(2^n n^2)$。关键在于如何求出 $g'$。

观察到：

$$g'_S=\sum_{P\cup Q\subseteq S, P\cap Q=\varnothing} 2^{\omega(S)-\omega(P)-\omega(Q)}=2^{\omega(S)}\sum_{P\cup Q\subseteq S, P\cap Q=\varnothing} 2^{-\omega(P)} \cdot 2^{-\omega(Q)}$$

这是子集卷积的形式，因此可以 $O(2^n n^2)$ 求出，故总时间复杂度为 $O(2^n n^2)$。

模板题（连通二分子图计数）：ARC105F Lights Out on Connected Graph | 提交记录

轻松砍下 vjudge 最优解，速度秒杀一片 $O(3^n)$ 的做法。

欧拉子图计数

给定一个 $n$ 个点 $m$ 条边的无向图，求其欧拉子图的数量。$1\leq n\leq 20$。

一个无向图是欧拉图，当且仅当其为连通图且每个点度数都为偶数。第一个条件可以用 $\ln$ 处理。那么只需要求出 $g_S$ 表示点集 $S$ 的导出子图的每个点度数均为偶数的子图数量，那么 $[z^S]\ln g$ 就是点集为 $S$ 的欧拉子图数量。

考虑第一个条件怎么求，不妨暴力枚举每一个点集 $S$，导出子图中的每条边可以看成一个二进制数，仅在端点位为 $1$，其余位为 $0$，那么 $g_S$ 就是选出一个非空子集异或和为 $0$ 的方案数。可以求出这些数的线性基 $V$，则 $g_S=2^{\omega(S)-(\dim V)}$。

考虑这个 $\dim V$ 是多少，根据此类问题的经验可以知道 $\dim V$ 即为点集 $S$ 的导出子图的生成森林边数（一个无向图的关联矩阵的秩，等于节点数减去连通块数，即生成森林边数，具体信息可以参考 北京大学离散数学课程的讲义）。这样就可以快速计算了。

时间复杂度 $O(2^n(n^2+m))$。

模板题：LibreOJ 6673 EntropyIncreaser 与山林 | 提交记录。

生成树计数 & 逐点牛迭

给定一个 $n$ 个点的无向图，求每个子图的生成树的数量。$1\leq n\leq 20$。

设 $f_S$ 表示点集为 $S$ 的生成树数量。考虑如何转移？我们可以任意选取一个代表元 $\epsilon(S)$，然后枚举 $\epsilon(S)$ 所在的连通块 $T$，然后在连通块 $T$ 和连通块 $S\backslash T$ 间连一条边即可。

但是这样会算重，注意到对于同一个生成树，我们实际上会多计算边数次，因为我们对于其中一个生成树的每条边 $(u,v)$，都会计算一次（注意不是两次）。因此可以得到下面的转移方程：

$$f_S=\frac{1}{|S|-1}\sum_{\substack{T\subseteq S\\ \epsilon(S)\in T}} f_T f_{S\backslash T} (\omega(S) - \omega(T) - \omega(S\backslash T))$$

边界 $f_{\{u\}}=1$。

直接做时间复杂度 $O(3^n)$，我们需要更优秀的做法。

沿用枚举代表元的思想，我们钦定 $\epsilon(S)=\max S$，这样我们就可以将所有集合按照 $\epsilon(S)$ 分组（排序），并且这样的顺序满足我们 dp 的需要。

考虑钦定转移时，总是不会在相同的 $\epsilon(S)$ 间转移，那么需要改写方程：

$$f_S = \sum_{\substack{T_1\sqcup T_2\sqcup\cdots \sqcup T_k = S\backslash \{\max S\}\\ \forall T_i, T_i\neq \varnothing \\ \text{Sets are unordered.}}} \prod_{i=1}^{k} f_{T_i} (\omega(T_i\cup \{\max S\}) - \omega(T_i))$$

它的意义是枚举 $\max S$ 的（编号小于自身）的邻域，然后将这些邻域合并起来。可以发现这个操作等价于 $\exp$。具体地，我们这样操作：

1. 枚举 $i$ 表示当前求解的集合的代表元（最大值）。
2. 构造集合幂级数 $g_S'=f_S\cdot (\omega(S\cup\{i\}) - \omega(S))$ 即权值。注意这里要求 $\max S < i$。
3. 计算 $g_S=\exp g_S'$。
4. 对于 $\max S = i$，令 $f_S\gets g_{S\backslash\{i\}}$。

分析一下时间复杂度：

$$\sum_{k=0}^{n} 2^k k^2 \sim O(2^n n^2)$$

枚举代表元，考虑代表元小于枚举值的集合对代表元为枚举值的集合的贡献，以便于采用集合幂级数理论优化递推的方法，称为 逐点牛顿迭代法。

稍后我们将看到一道相关的例题 We Love Forset。

胡策的统计

QOJ 4259 集训队互测 2015 Round 3 A. 胡策的统计。

给定一个 $n$ 个点的无向图。定义一个图的权值为其连通块数量的阶乘。求其所有生成子图的权值之和。$1\leq n\leq 20$。

观察到这个连通块数量的阶乘非常奇怪，像极了忘记给连通块去重（bushi），也就是说错误地给组合连通块加上了顺序的限制。

令 $g_S$ 表示点集为 $S$ 的导出子图数量，则 $g_S=2^{\omega(S)}$，令 $f'\gets \ln g$，那么 $f_S$ 表示点集为 $S$ 的导出连通子图数量。

我们可以将题意看成将若干个连通块按照顺序连接，这对应 Sequence 构造。令 $f_S$ 表示点集为 $S$ 的导出子图的权值之和，那么 $f=\frac{1}{1-f'}$。

集合幂级数 $\ln$ + 求逆即可。时间复杂度 $O(2^n n^2)$。提交记录。

We Love Forest

ABC253Ex We Love Forest。

给定含 $m$ 条边的可重集和一个 $n$ 个点的图（初始时图中没有边）。从时刻 $1$ 开始，你可以选择一条边，将这条边添加到图中（不从可重集中删除）。对于每一个 $i\in[1,n)$，求时刻 $i$ 时，该图为森林的概率。

原数据范围 $2\leq n\leq 14$。不妨加强为 $2\leq n\leq 18$。

若计算出时刻 $i$ 时该图为森林的方案数，则乘上 $\frac{i!}{m^i}$ 即转变为概率（假设这个方案中加边是无序的）。先采用之前的方法，逐点牛顿迭代 $O(2^n n^2)$ 求出每个点集 $S$ 的导出子图的生成树数量 $f_S$。

然后你发现我们要做的是一个类似 $\exp$ 的操作（森林是由许多树组合而成的）。不过这中途不方便记录边数，因此我们不妨采用二元生成函数，对 $f$ 的占位多项式取做 $\exp$。

具体地，对于一个树，我们给它附一个占位元 $x$（一次），这样求 $\exp$ 后，只需要取 $x^{i}$ 项系数就可以得到 $i$ 个树构成的森林（$n-i$ 条边构成的森林）的方案数了。

时间复杂度看起来是 $O(2^n n^4)$（$O(n^2)$ 求 $\exp$ + $O(n^2)$ 多项式乘法），不过实际实现时总是一个多项式乘一个一次式，所以时间复杂度实际上是 $O(2^n n^3)$，比常规的 $O(n3^n)$ 算法快一些。

提交记录 $O(n3^n)$ | 提交记录 $O(2^n n^3)$。

Hierarchical Phylogeny

AtCoder Xmas Contest 2020 H Hierarchical Phylogeny。

给定 $n$ 和两个集合 $L,R$，构造点数位于 $(0,2^n]$，编号位于 $(0,2^n]$ 的有根树，满足：

• 一个点要么为叶子，要么有两个子节点。
• $L$ 中的所有点均为叶子（反之亦然）。根节点在 $R$ 中。
• 对于非叶子 $C$，若其两个子节点为 $A,B$，则满足 $A\cap B=\varnothing\land A\cup B=C$。

$1\leq n\leq 21$。

题目给定的限制直接明示了子集卷积，因此可以尝试采用用卷积刻画题目约束的树结构。

令 $f_S$ 表示 $S$ 为根的树的数量，那么不难写出：

$$f = \mathbf{L} + \frac{1}{2} f^2\implies f = 1-\sqrt{1-2 \mathbf{L}}$$

其中 $\mathbf{L}$ 表示一个集合幂级数满足 $\mathbf{L}_S = [S\in L]$。我们舍弃了 $1+\sqrt{1-2 \mathbf{L}}$ 的解因为它显然是不成立的。

于是只需要对集合幂级数开根就可以得答案了。时间复杂度 $O(2^n n^2)$，提交记录。

最后我们用 官方题解 中的一段话来结束本节：

特に中国で元々有名だった手法です．あまりちゃんと調査を行っていないのですが，中国の IOI 選抜に使われる論文がこの手の応用のおそらくきっかけです．中国語で「子集卷积」 (subset convolution) やら「集合幂级数」 (set power series) やらを検索することで情報がわんさか出てきますね．日本で話題になったのは ARC 105 のときで，Elegia さんの書き込みのおかげで知れ渡る形となりました．

好吧我并不认为集合幂级数是【元々有名だ】，它事实上还挺小众的（相对于中国的庞大基数而言）。

无环限制与强连通性限制

DAG 定向计数

给定一个 $n$ 个点的无向图，你将每条边定向，使得这个图变成一个 DAG。求方案数。$1\leq n\leq 20$。

有一个比较经典的 $O(3^n)$ 的 DAG 容斥做法。

DAG 容斥速通

我们设 $f_S$ 表示点集为 $S$ 的导出子图定向为 DAG 的方案数，那么有：

$$f_S=\sum_{\substack{T\subseteq S,T\neq \varnothing \\ T\text{ is an independent set}}} f_{S\backslash T} (-1)^{|T|+1}$$

注意这里的 $(-1)^{|T|+1}$ 是容斥系数。采用容斥是因为不确定 $S\backslash T$ 是否存在不与 $S$ 相连的点，需要容斥掉。由于 $\sum_{T\subseteq S,T\neq \varnothing} (-1)^{|T|+1}=1$，所以这是一个良好的容斥系数。这个做法被称为 DAG 容斥。

直接转移的时间复杂度为 $O(3^n)$。

沿用 DAG 容斥的思路，不过我们尝试换一个角度看这个 dp。我们发现 dp 其实在做这样一件事情：选出若干个独立集，独立集 $T$ 的权值为 $(-1)^{|T|+1}$。你需要让所有选出的独立集都不交，且并集为 $\{1,2,\cdots,n\}$，求方案数。这个形式让我们联想起集合幂级数理论。

不妨取集合幂级数 $g$，$g_S=[S\neq \varnothing](-1)^{|S|+1} [S \text{ is an independent set}]$。那么有：

$$f=\sum_{k\geq 0} g^k=\frac{1}{1-g}$$

那么只需要做一遍集合幂级数求逆就可以在 $O(2^n n^2)$ 的时间复杂度内求出 $f$ 了。

模板题（原题意答案要乘上 $\frac{m}{2}$）： CEOI 2019 Amusement Park | 提交记录

子图 DAG 定向计数

给定一个 $n$ 个点的无向图，选出一个子图并将每条边定向，使得这个子图变成一个 DAG。求方案数。$1\leq n\leq 20$。

考虑 DAG 容斥，设 $f_S$ 为点集为 $S$ 的子图定向为 DAG 的方案数，那么有：

$$f_S = \sum_{T\subseteq S,T\neq \varnothing} f_{S\backslash T} (-1)^{|T|+1} 2^{\omega(S) - \omega(T) - \omega(S\backslash T)}$$

直接做是 $O(3^n)$ 的，可以尝试用集合幂级数理论优化。

先变形一下，令 $f_S\gets f_S 2^{-\omega(S)}$：

$$f_S = \sum_{T\subseteq S,T\neq \varnothing} f_{S\backslash T} (-1)^{|T|+1} 2^{-\omega(T)}$$

这又是一个形如 Sequence 构造的东西，令 $g_S=[S\neq \varnothing](-1)^{|S|+1}2^{-\omega(S)}$，那么有：

$$f = \frac{1}{1-g}$$

集合幂级数求逆即可，时间复杂度 $O(2^n n^2)$。

DAG 子图计数

给定一个 $n$ 个点的有向图，求其 DAG 子图个数。$1\leq n\leq 15$。

放这道题是为了展示集合幂级数的局限性，它不能优化所有的子图计数状压 dp。

考虑 DAG 容斥，设 $f_S$ 为点集为 $S$ 的子图定向为 DAG 的方案数，那么有：

$$f_S = \sum_{T\subseteq S,T\neq \varnothing} f_{S\backslash T} (-1)^{|T|+1} 2^{\omega(S\to T)}$$

这个形式很难优化（关键在于 $\omega(S\to T)$ 很难处理），如果有人会优化到低于 $O(3^n)$ 可以联系我。

参考资料

• 陈昕阳 《集合幂级数在子图计数问题上的应用》（APIO 2025 演讲）
• 吕凯风《集合幂级数的性质与应用及其快速算法》（国家集训队 2015 年论文）
• maspy 集合べき級数関連 (4) 問題例
• ToStars 此间最是少年忆难断【生成子图划分及容斥问题】
• x义x 集合幂级数学习笔记
• PengAo 生成子图计数问题学习笔记