浅谈集合幂级数

大家好我又来开新坑啦！ 另外声明一下，这篇文章也不会用传统的方式介绍集合幂级数的知识，结构大概同样会参考 EI 的论文。 # 前言 作者是个民科 OIer，所写内容可能包含巨大多理论错误或常识性错误，敬请读者一一指出或喷作者。 ## 定义 ### 经典定义 设全集 $U = \{1,2,\dots,n\}$，将经典的生成函数未定元的上指标定义在 $U$ 的幂集 $2^U$ 上，将卷积定义在上指标两个集合 $S,T$ 的无交并上。 关于无交并，我们认为当 $S \cap T = \varnothing$ 时 $x^S \cdot x^T = x^{S \cup T}$，否则 $x^S \cdot x^T = 0$。 即，把形式幂级数的 $x$ 的指数换成 $U$ 的子集，卷积时仅对不相交的两个集合定义加法，为其并。 但注意和其他领域中的无交并区分，它们可能具有不同的定义。 ### 多元幂级数定义 我们直接把集合幂级数看成 $n$ 元的幂级数，令一个集合 $S \subseteq U$，那么其对应的未定元为 $\prod_{i\in S} x_i$。 我们令这样的幂级数的运算均在 $\bmod x_1^2 \bmod x_2^2 \cdots \bmod x_n^2$ 意义下进行，可以发现有交的集合的并就恰好溢出到了 $2$ 以外，相当于被截断了。假设系数的交换环为 $\mathbb A$，那这就可以记为 $\mathbb A[x_1, \dots, x_n]/(x_1^2,\dots,x_n^2)$。 这样的定义其实是更自然的，更便于叙述其代数性质。 ## 卷积 ### 卷积 我们注意到上述定义的卷积其实就是「子集卷积」。那么在了解基本的「集合并卷积」的前提下，这件事的解决方案是很简单的。 具体地，我们在运算时为集合幂级数添加一个维度来记录其集合大小，显然当 $S \cap T \ne \varnothing$ 时，$|S\cap T| < |S|+|T|$。这样就可以区分出应当溢出的值。这样，对这个维度每个值逐次进行快速莫比乌斯变换，再在这个维度上进行一般的卷积，再作快速莫比乌斯逆变换即可。 事实上，这个新的维度其实就是所谓「占位多项式」。 若记长度为 $n$ 的多项式乘法的复杂度为 $\mathsf M(n)$，那么其复杂度为 $O((\mathsf M(n) + n^2) 2^n)$，不过一般来说可以直接记作 $O(n^2 2^n)$。 ### 在线卷积 #### 半半在线卷积 注意到上述算法描述的过程可以直接支持在线卷积，也即在集合大小从小到大时将占位多项式的卷积改为在线卷积，实践中可以直接用 $\Theta(n^2)$ 实现。 这样，每次计算出同一个大小的所有集合在莫比乌斯变换下的结果之后，如果还需要额外的**松弛**（即在线卷积中计算出卷积结果后进行的额外计算），就需要先作逆变换处理再变换回来，否则直接一路卷积即可。 经典地，可以参考[「WC2018」州区划分](https://www.luogu.com.cn/problem/P4221)。 总复杂度是 $\Theta(n^2 2^n)$。 不过，相对地，如果我们试图按照集合的二进制数从小到大进行计算半在线卷积，则需要使用**全半在线卷积**（本文不予提及，请参考 EI 论文原文）；而这种算法称为**半半在线卷积**。 #### 转化为形式幂级数 沿用子集卷积的思路，直接在莫比乌斯变换后的结果上执行形式幂操作即可。 相关的操作有形式幂级数求逆、指数对数等。 对于这些，只需要在莫比乌斯变换后求解这些操作对应的微分方程即可（也即直接在占位多项式上执行这些操作）。 事实上这一思想还是比较简单的，并且在下文多次出现。 ## 逐点牛顿迭代法 考虑计算集合幂级数 $F$ 时，我们按照其最高位逐点计算，若当前最高位是 $n$，且我们已经计算出 $[x_n^0]$，并且可以用 $\Theta(f(n))$ 的时间计算 $[x_n^1]$，那么总复杂度也是 $\Theta(f(n))$ 的，其中 $f(n) = \Omega(2^n)$。 ### 例：无根树计数 > 给定一无向完全图的邻接矩阵 $\mathbf G$，对每个非空点集 $S$，求其所有点集为 $S$ 的生成树的边权积的和。 我们考虑按点的编号从小到大组合出所有子集的生成树。 考虑当前的最大点为 $n$，若已计算出点的编号 $<n$ 的所有答案，则考虑假定 $n$ 为根，将其组合成 $[x_n^1]$。 首先我们考虑每个 $<n$ 的点集 $T$，若其作为新生成树的一个连通块，则可以任意选择子树的根与 $n$ 连接，也即乘上 $\sum_{j\in T} \mathbf G_{jn}$，然后作集合幂级数的指数运算即可得到 $[x_n^1]$。 总时间复杂度 $\Theta(n^2 2^n)$。 ### 复合 这次我们用一个递归描述问题。 若要对集合幂级数 $G$，多项式 $f$，求算 $F = f(G)$，那么注意到 $F' = f'(G) G'$，其中求导是 $\frac{\partial}{\partial x_n}$，提取 $[x_n^0]$ 即得 $$ [x_n^1] F = ([x_n^1] G) \cdot ([x_n^0] f'(G)) $$ 而常数项被损失，因此我们需要计算 $$ [x_n^0] F = [x_n^0] f(G) $$ 这显然可以递归到 $n-1$ 的问题。而注意到每次问题中的 $f$ 只会增加一个，则复杂度为 $$ \sum\limits_{k=0}^n (n-k) \cdot \Theta(k^2 2^k) = \Theta(n^2 2^n) $$ 这个做法可以扩展到更多元的 $f$ 进行复合，且这个做法如果进行通用的常数优化，会比一般人写的特化的集合幂级数 exp 等算法**达到更优的效率**！ 此外，一个显著的优化是在执行算法的过程中保持莫比乌斯变换的结果，再经过若干精细实现可以做到 $\Theta(\mathsf M(n) 2^n)$。 我们将看到，这一算法有很多的应用。 #### 例：P6570 优秀子序列 模仿在形式幂级数上处理类似乘积的做法，用 $\ln$ 和 $\exp$ 展开，问题就变成了集合幂级数的 $\exp$。 #### 例：UOJ 94 胡策的统计 从生成子图个数到连通生成子图个数间无非只差了一个 $\ln$，而再到答案则只差了一个 $\frac1{1-*}$ 的复合。 可以利用上述算法直接计算 $\frac1{1-\ln *}$。 #### 例：Tutte 多项式 我们考虑一个图 $G=(V,E)$ 的 Tutte 多项式 $$ T_G(x,y) = \sum\limits_{A\subseteq E} (x-1)^{k(A)-k(E)} (y-1)^{k(A)+|A|-|V|} $$ 其计算统一了几个经典的图论计数问题。 不过理论意义暂且不提，我们来讲讲如何求算一组点值。 容易知道指数都是非负的，因此我们可以尝试给出一个在任意环上的算法。 首先我们知道其 Tutte 多项式等价于每个连通分量的 Tutte 多项式的乘积。因此不妨先假设 $G$ 为连通图。 考虑 $A$ 作为边集时的一个连通分量 $S$，令其导出子图的边集为 $B$，则定义其权值 $$ f_S(B) = (y-1)^{k(B)+|B|-|S|} = (y-1)^{|B|-(|S|-1)} $$ 于是对于 $A$，其在 $G$ 的 Tutte 多项式中的贡献即为各个连通分量的 $f$ 的乘积乘上 $(x-1)^{k(A)-k(E)} = (x-1)^{k(A)-1}$。 因此若定义 $g_S$ 为 $\sum f_S(B)$，其中 $B$ 使得 $S$ 为一个连通分量，则 $G$ 的 Tutte 多项式即为 $$ [w^V] \sum\limits_{i\ge 1} (x-1)^{i-1} \frac{\left(\sum_{S \ne \varnothing} g_S w^S\right)^i}{i!} $$ 这个地方可以直接调用如上算法计算复合。 但是如果我们考虑给每个 $g_S$ 乘进一个 $x-1$，然后想办法除掉一个贡献（比如强制去掉编号最小的结点所在连通分量的贡献）即可转化为 exp。 并且，容易发现这个东西可以直接扩展到任意图上而不需要其他操作。 然后下一步是求出 $g_S$。考虑进行逐点牛顿迭代。 对于 $S \ni n$，考虑从 $S$ 中删去 $n$ 所构成的连通分量。 若一个连通分量与 $n$ 连有 $m$ 条边，则其贡献为 $$ \sum\limits_{i=1}^m \binom mi (y-1)^i = y^m-1 $$ 然后由于新加入的点，需要另外除以一个 $y-1$。有趣的是由于这个东西恰好就是等比数列求和，所以可以方便地预处理。 时间复杂度 $\Theta(n^2 2^n)$。 ## 复合方程 终究还是要来的。 定义同[多元拉格朗日反演中提到的树形复合方程](https://www.luogu.com.cn/blog/your-alpha1022/qian-tan-duo-xiang-shi-fu-ge-hu-la-ge-lang-ri-fan-yan)。 以下记 $f^S = \prod\limits_{i\in S} f_i$。 ## 一项系数 照搬多元拉格朗日反演。 由 $$ [x^S] H(\mathbf F) = [x^S] H G^S \left\lVert[i=j]-\frac{x_j}{G_i(\mathbf x)}\frac{\partial G_i(\mathbf x)}{\partial x_j}\right\rVert $$ 经过 $\tilde O(2^n)$ 的预处理（实践中一个容易想到的做法无非是 $\Theta(n^3 2^n)$ 的），可以做到 $\Theta(|S|^2 2^{|S|})$。 ### 所有系数 我们首先设计一个算法来验证一组解是否正确。 则核心问题是计算 $n$ 组复合 $G_i(\mathbf F)$。 考虑复合 $P(\mathbf F)$。 考察逐点牛顿迭代法，考虑 $[x_n^0] \frac{\partial}{\partial x_n} P(\mathbf F),[x_n^0] P(\mathbf F)$，则注意到 $$ [x_n^0] \frac{\partial}{\partial x_n} P(\mathbf F) = \sum\limits_{k=1}^n \left[[x_n^1] \left(\frac{\partial}{\partial x_k} P\right)(\mathbf F)\right] \cdot \left[[x_n^0] \frac{\partial}{\partial x_n} F_k\right] $$ 因此 $[x_n^1] \left(\frac{\partial}{\partial x_k} P\right)(\mathbf F) = [x_n^0] \frac{\partial}{\partial x_n} \left(\frac{\partial}{\partial x_k} P\right)(\mathbf F)$ 可以继续递归，而 $[x_n^0] P(\mathbf F)$ 也可以递归。 考虑规模为 $n-k$ 的子问题，容易发现这减少的 $k$ 次是从某一次开始一直递归到 $\frac{\partial}{\partial x_n}$，而每次递归到此会从 $n$ 个元中选出一个递归，因此对应的问题个数是 $\sum\limits_{i\le k} \binom ni$。 而还有一个观察是，对于规模为 $n-k$ 且形式为 $\left(\prod\limits_{i\in S} \frac{\partial}{\partial x_i}\right) P(\mathbf F)$ 的子问题，其中 $i\le n-k$ 的部分无需考虑含 $x_i$ 的系数，因为在回溯贡献到最终答案的过程中，这部分的值都被溢出了。 于是总共的卷积规模是 $$ T(n) = \sum\limits_{i+j\le k} \binom{n-k}i \binom kj 2^{n-k-i} $$ 接下来证明其规模是 $\Theta(\alpha^n)$ 的，其中 $\alpha = \frac{3+\sqrt 5}{2} \approx 2.618$。 考虑 $$ \begin{aligned} T(n) &= \sum\limits_{i+j\le k} \binom{n-k}i \binom kj 2^{n-k-i} \\ &= \sum\limits_{i+j+t=k} ([z^i] (2+z)^{n-k})([z^j] (1+z)^k) \left([z^t]\frac1{1-z}\right) \\ &= \sum\limits_{k\le n} [z^k] \frac{(2+z)^{n-k}(1+z)^k}{1-z} \\ &= [z^0]\sum\limits_{k\le n} \frac{(2+z)^{n-k}(1+z)^k}{z^k(1-z)} \\ &= [z^0]\sum\limits_{k\ge 0} \frac{(2+z)^k(1+z)^{n-k}}{z^{n-k}(1-z)} \\ &= [z^n]\frac{(1+z)^n}{1-z} \sum\limits_{k\ge 0} (2+z)^k(1+z)^{-k} z^k \\ &= [z^n](1+z)^n \frac{1+z}{(1-z)(1-z-z^2)} \\ &= [z^n]\frac{(1+z)^2}{(1-z)(1-z-z^2)} \cdot \frac1{(1+z)^2} \cdot \left(\frac z{z(1+z)^{-1}}\right)^{n+1} \\ &= [z^n]\frac{1-z}{(1-2z)(1-3z+z^2)} \end{aligned} $$ 因式分解可得其增长率被特征根 $\alpha,\beta,\gamma = \frac{3\pm \sqrt 5}2,2$ 中最大的 $\alpha$ 控制，故其为 $\Theta(\alpha^n)$。 这样，我们按照子集卷积改写为半在线子集卷积的过程，将其改写为一个在线的过程，即可得到求解其问题的算法。时间复杂度 $\Theta(n \alpha^n \mathsf R(n))$，其中 $\mathsf R(n)$ 为执行半在线卷积的复杂度。 ### 对称复合方程 对于特殊的情况，我们能做到一些更好的复杂度。 #### 定义 对于一组由 $\mathbf G$ 定义的树形复合方程 $\mathbf F$，若存在集合幂级数 $\mathscr B$，其有值项的度数均 $\ge 2$，和一族 EGF $g_1,g_2,\dots,g_n$ 使得 $$ G_i = g_i' \left(\frac{\partial}{\partial x_i} \mathscr B\right) $$ 则称该方程是对称的。 #### 一个结论及其组合意义 对于上述对称复合方程 $\mathbf F$，存在集合幂级数 $\mathscr C$ 使得 $$ g_i\left(\left(\frac{\partial}{\partial x_i}\mathscr B\right)(\mathbf F)\right) = \frac{\partial}{\partial x_i}\mathscr C $$ 我们考察**圆方树**。 对集合幂级数的每个元，我们视作其描述了圆点的集合。 对于每棵圆方树，我们对**每个圆点**按其度数赋予一个权值，并对**所有方点**按其邻接点集赋予一个权值。 则整棵圆方树的权值是其所有点的权值之积，其幂级数即对所有圆方树的权值求和。 则 $\mathscr C$ 可以视作是对所有圆方树作统计，其中 $[x^S] \mathscr C$ 描述了圆点点集为 $S$ 时的权值和。取其 $\frac{\partial}{\partial x_i}$ 可以看做是考察了圆点 $i$ 所在的连通块，或将其视为连通块的根。 而 $g_i$ 描述了圆点 $i$ 各个度数对应的权值，$[x^S] \mathscr B$ 描述了方点的邻接点集对应的权值。 这样，无论是对复合方程本身或是以上结论的解释都是完备的，且有几分优美。 当然也可以从圆方树溯源到无向图本身来理解，但是这里为了承接**树形**复合方程，就利用圆方树来解释了。 #### 求解 对于给定的 $g_i$，我们可以在 $\Theta(n2^n \mathsf M(n))$ 内完成 $\mathscr B$ 到 $\mathscr C$ 的变换。 这一算法首先由论文哥 negiizhao 提出  我们先考虑一个退化的平凡情形：$g_i=x$，则 $\mathscr C = \mathscr B$。 而若我们首先将 $g_1$ 改成任意 EGF，则相当于将圆点 $1$ 的邻接方点进行组合，即 $\frac{\partial}{\partial x_1}\mathscr C = g_1\left(\frac{\partial}{\partial x_1}\mathscr B\right)$。 类似地，我们考察进行一组变换 $\mathscr B = \mathscr T_0 \to \mathscr T_1 \to \cdots \to \mathscr T_n = \mathscr C$。即在过程中逐个将 $g_i$「一般化」。因此第 $i$ 步会进行 $$ \begin{aligned} \frac{\partial}{\partial x_i} \mathscr T_i &= g_i\left(\frac{\partial}{\partial x_i}\mathscr T_{i-1}\right) \\ \left.\mathscr T_i\right\vert_{x_i=0} &= \left.\mathscr T_{i-1}\right\vert_{x_i=0} \end{aligned} $$ 直接计算就可以得到 $\Theta(n^3 2^n)$ 的算法，但若我们考虑始终保持莫比乌斯变换的形式计算，则可以将复杂度优化到 $\Theta(n 2^n \mathsf M(n))$，可以减小常数。 ##### 连通-点双连通变换 这是该算法[提出之初](https://loj.ac/d/2668)想解决的问题，其被称为**连通-点双连通变换**。 发现取 $g_i = \exp x$，则 $\mathscr B,\mathscr C$ 可以描述同一张无向图的所有点集的导出子图的连通子图数量和点双连通子图数量。 则我们将这一算法每一步都逆过来，即可得到其解法。 当然，顺着做的就是**点双连通-连通变换**。 ###### 例：数仙人掌 > 给定无向简单图 $G=(V,E)$，问有多少个 $E$ 的子集使得图连通且每个点最多在一个简单环中。对 $998244353$ 取模。 每个点双连通分量显然是一条边或一个简单环。通过状压 DP 容易计算出其对应的集合幂级数。 然后执行点双连通-连通变换即可。 ## 参考资料 - EI 论文。