集合幂级数科技模板题

· · 题解

我们先来计算各个点集的导出子图的生成树个数。

考虑枚举 k=1,\dots,n，依次计算所有 S \subseteq \{1,\dots,k\} 的答案。
考虑每次加入一个点 k+1，对于 S \subseteq \{1,\dots,k\}，我们考虑如何在其中加入 k+1。
自然只需枚举断开 k+1 后会构成哪些连通块，不难发现这就是一个集合幂级数的 exp 操作。

核心代码（执行完后 f_S 为 S 导出子图的生成树个数，e_u 为邻接矩阵，\exp 表示将 f_{2^k,\dots,2^{k+1}-1} 原地 \exp）：

f[0] = 1;
for (int k = 0; k < lg; ++k) {
  for (int i = 0; i < (1 << k); ++i) f[i + (1 << k)] = (ll)f[i] * popcnt(e[k] & i) % mod;
  Set::exp(f + (1 << k), f + (1 << k), k);
}

时间复杂度由 T(n) = T(n-1) + O(n^2 2^n) 得到，为 O(n^2 2^n)。
从而这也叫做逐点牛顿迭代法。

接下来，问题为给定集合幂级数 F(x)，对于 k=0,\dots,n 计算 [x^U] F^k(x)。
我们不妨泛化为给定系数序列 b_S，计算序列

a_k = \sum_{S\subseteq U} b_S [x^S] F^k(x)

将其转置，即得

b_S = [x^S] \sum_{k=0}^n a_k F^k(x)

这就是一般的多项式复合集合幂级数问题，应用逐点牛顿迭代法也可以做到 O(n^2 2^n)。
具体地，对于 f, G，令 F = f(G)。在两边作用 \frac{\partial}{\partial x_n}（相当于取 [x_n^1]），可得

\frac{\partial}{\partial x_n} F = f'(G) \cdot \frac{\partial}{\partial x_n} G

也就是说，若令 G_k(x) = G(x) | _{x_n=x_{n-1}=\dots=x_{n-k+1}=0}，则对于 G_{n-k} 我们需要计算 f,f',\dots,f^{(k)} 复合 G_{n-k} 的结果。
如此递归，复杂度为 \sum_{k\ge 0} (n-k) \cdot k^2 2^k = O(n^2 2^n)。
如预处理 G_{0,\dots,n} 的 FMT 数组，常数会更小。