OI-wiki 符号化方法Symbolic Method实战指南用组合构造统一生成函数推导【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读符号化方法symbolic method是把「组合对象」与「生成函数」建立一一对应的一套系统化技术你只需把组合类拆解成若干标准构造并、积、Sequence、Multiset、Powerset、Cycle就能机械地写出其普通生成函数OGF的方程。本文以 docs/math/poly/symbolic-method.md 为主体系统讲解无标号体系下的六大构造及其 OGF 运算、有限制带参构造与 Pólya 算子准逆、指数、对数并给出分拆数、付公主的背包、无标号树、烷基计数等完整例题推演。读完后你将掌握用「组合类方程 → 生成函数方程 → 系数提取」三步走解决一类计数问题的完整套路并理解多项式 exp / ln 运算在组合计数中的底层含义。背景为什么需要符号化方法在 OI 的计数问题中我们常遇到「求满足某结构的对象个数」。直接枚举往往不可行而生成函数提供了一条自动化路径只要能写出组合类的构造方程生成函数方程就自动成立剩下的只是多项式运算。这正是本方法在 docs/math/poly/ 这一章中的位置——它是 OGF/EGF 理论与多项式算法FFT/NTT、exp、ln之间的桥梁。在 OI-wiki 的生成函数章节中普通生成函数 和 指数生成函数 提供了基础运算与封闭形式而符号化方法则回答「如何系统地得到这些生成函数」这一关键问题。从仓库源码可以看到这套方法在真实计数代码中确实被直接使用例如 graph-enumeration_1.cpp 中通过ln/exp从「所有图」的生成函数反推「连通图」「欧拉图」「二分图」的计数正是符号化方法「无标号/有标号构造 对数与指数算子」的工程实现。基本概念组合类与生成函数一个组合类combinatorial class记作 $(\mathcal{A},\lvert \cdot \rvert)$其中 $\mathcal{A}$ 是组合对象的集合$\lvert \cdot \rvert$ 是大小函数size function将每个对象映射为一个有限的非负整数。例如字符集为 ${0,1}$ 的字符串大小函数可取字符串长度树或图大小函数可取节点数量大小函数并非绝对也可以将某些特定节点的大小设为 $0$。本文讨论的是无标号体系unlabelled对应使用普通生成函数OGF。对于集合 $\mathcal{A}$其 OGF 为$$ A(z)\sum_{\alpha\in\mathcal{A}}z^{\lvert \alpha \rvert}\sum_{n\geq 0}a_nz^n $$约定用同一组字母表示同一个类及其生成函数例如 $a_n[z^n]A(z)$$\mathcal{A}_n$ 表示大小函数为 $n$ 的对象集合因此 $a_n\operatorname{card}(\mathcal{A}_n)$card 为基数/cardinality。本文不讨论可容许性admissibility条件相关内容可参考 Analytic Combinatorics 原著该文档即基于其第一章的简化见 docs/math/poly/symbolic-method.md。两个基础类中性类与原子类名称记号对象大小OGF中性对象/中性类$\epsilon$ / $\mathcal{E}{\epsilon}$单个中性对象$0$$E(z)1$原子对象/原子类$\circ$ 或 $\bullet$ / $\mathcal{Z}{\circ}{\bullet}$单个原子对象$1$$Z(z)z$两个组合类在组合意义上同构记为 $\mathcal{A}\mathcal{B}$ 或 $\mathcal{A}\cong\mathcal{B}$后者仅在同构不平凡时使用。显然有$$ \mathcal{A}\cong\mathcal{E}\times \mathcal{A}\cong\mathcal{A}\times\mathcal{E} $$其中 $\times$ 为二元运算表示集合的笛卡尔积。这相当于说中性对象是笛卡尔积的单位元原子对象是最小的「积木块」。无标号体系的五大基础构造并构造Disjoint Union / Sum类 $\mathcal{A}$ 与 $\mathcal{B}$ 的并记为$$ \mathcal{A}\mathcal{B}(\mathcal{E}_{1}\times\mathcal{A})(\mathcal{E}_2\times\mathcal{B}) $$引入 $\mathcal{E}_1,\mathcal{E}_2$ 两个不同的中性对象是为了不违背集合论中「集合不相交」的要求——可以想象成把 $\mathcal{A}$ 的对象染成红色、$\mathcal{B}$ 的对象染成蓝色。对应 OGF 为$$ A(z)B(z)\sum_{n\geq 0}(a_nb_n)z^n $$即形式幂级数的加法类的并 → OGF 相加。笛卡尔积构造Cartesian Product类 $\mathcal{A}$ 与 $\mathcal{B}$ 的笛卡尔积为$$ \mathcal{A}\times \mathcal{B}{(\alpha,\beta)\mid \alpha\in\mathcal{A},\beta\in\mathcal{B}} $$定义 $(\alpha,\beta)$ 的大小为其组成部分大小之和$$ \gamma(\alpha_1,\alpha_2,\dots,\alpha_n)\implies \lvert\gamma\rvert\lvert\alpha_1\rvert\cdots\lvert\alpha_n\rvert $$对应 OGF 为$$ A(z)\cdot B(z)\sum_{n\geq 0}\sum_{ijn}a_ib_jz^n $$即形式幂级数的乘法卷积类的积 → OGF 相乘。这正是「多个部件组合成一个整体时方案数做卷积」这一直觉的形式化。Sequence 构造有序的组合Sequence 构造生成所有有序的有限序列$$ \operatorname{SEQ}(\mathcal{A})\mathcal{E}\mathcal{A}(\mathcal{A}\times \mathcal{A})(\mathcal{A}\times \mathcal{A}\times \mathcal{A})\cdots $$要求 $\mathcal{A}_0\varnothing$即 $\mathcal{A}$ 中没有大小为 $0$ 的对象否则会出现无限多种表示。以下例说明「有序」的含义$$ \begin{aligned} \operatorname{SEQ}({a}){\epsilon}{a}{(a,a)}{(a,a,a)}\cdots\ \operatorname{SEQ}({a,b}){\epsilon}{a,b}{(a,b)}{(b,a)}{(a,a)}{(b,b)}\cdots \end{aligned} $$可以看到 ${(a,b)}$ 与 ${(b,a)}$ 被同时生成即组成部分的顺序不同视为不同对象。对应 OGF 为$$ Q(A(z))1A(z)A(z)^2A(z)^3\cdots\frac{1}{1-A(z)} $$其中 $Q$ 为Pólya 准逆quasi-inversion。例有序有根树ordered rooted tree。设组合类为 $\mathcal{T}$一棵树 一个根节点 子树的有序序列$$ \mathcal{T}{\bullet}\times\operatorname{SEQ}(\mathcal{T}) $$对应 OGF 方程$$ T(z)\frac{z}{1-T(z)} $$解得 $T(z)$ 的系数正是 Catalan 数前几项为0 1 1 2 5 14 42 132 429 1430 4862 16796忽略常数项即 OEIS A000108。这正是 OI 中「卡特兰数的代数推演」见 docs/math/combinatorics/catalan.md 的相关内容以及 ogf.md 中卡特兰数生成函数的推导在符号化方法框架下的统一表达。Multiset 构造无序多重集Multiset 构造生成所有可能的组合但不区分组成部分的顺序$$ \operatorname{MSET}(\mathcal{A})\prod_{\alpha\in\mathcal{A}}\operatorname{SEQ}({\alpha}) $$且要求 $\mathcal{A}_0\varnothing$。等价地可以写成商形式$$ \operatorname{MSET}(\mathcal{A})\operatorname{SEQ}(\mathcal{A})/\mathbf{R} $$其中 $\mathbf{R}$ 是等价关系$(\alpha_1,\dots,\alpha_n)\mathbf{R}(\beta_1,\dots,\beta_n)$ 当且仅当存在置换 $\sigma$ 使得对所有 $j$ 有 $\beta_j\alpha_{\sigma(j)}$。对比两个例$$ \begin{aligned} \operatorname{MSET}({a}){\epsilon}{a}{(a,a)}{(a,a,a)}\cdots\ \operatorname{MSET}({a,b}){\epsilon}{a}{(a,a)}{(a,a,a)}\cdots{b}{(a,b)}{(a,a,b)}\cdots \end{aligned} $$${(b,a)}$、${(a,b,a)}$ 在 $\operatorname{SEQ}$ 中出现但不在 $\operatorname{MSET}$ 中出现体现了「无序」。对应 OGF 为Pólya 指数Euler 变换$$ \operatorname{Exp}(A(z))\prod_{\alpha\in\mathcal{A}}\left(1-z^{\lvert\alpha\rvert}\right)^{-1}\prod_{n\geq 1}\left(1-z^n\right)^{-a_n} $$利用 $\ln(1z)\sum_{n\geq 1}\frac{(-1)^{n-1}z^n}{n}$ 与 $A(z)\exp(\ln A(z))$可展开为$$ \operatorname{Exp}(A(z))\exp\left(\frac{A(z)}{1}\frac{A(z^2)}{2}\frac{A(z^3)}{3}\cdots\right) $$这就是计数中最常遇到的「多项式 exp」运算MSET 构造 → OGF 上的 ExpEuler 变换。在 docs/math/poly/elementary-func.md 中多项式 $\exp$ 的算法正是在模意义下实现该算子而 graph-enumeration_1.cpp 中ln/exp的对偶使用则展示了 Exp 与 Log 互为逆运算的实际调用关系。例题分拆数LOJ 6268题意令 $f(n)$ 表示将 $n$ 分拆的方案数求 $f(1),\dots,f(10^5)$ 对 $998244353$ 取模的值。解设全体正整数类为 $\mathcal{I}$则 $\mathcal{I}\operatorname{SEQ}_{\geq 1}(\mathcal{Z})\mathcal{Z}\times\operatorname{SEQ}(\mathcal{Z})$下标 $\geq 1$ 为有限制构造见下文。所求即$$ \operatorname{MSET}(\mathcal{I}) $$其 OGF 前几项系数为1 2 3 5 7 11 15 22 30 42忽略常数项即 OEIS A000041。例题付公主的背包洛谷 P4389题意给出 $n$ 种体积分别为 $v_1,\dots,v_n$ 的商品和正整数 $m$求体积为 $1,2,\dots,m$ 的背包装满的方案数商品数量不限同体积可有不同种商品对 $998244353$ 取模。约定 $1\leq n,m\leq 10^5$$1\leq v_i\leq m$。解设商品的组合类为 $\mathcal{A}$所求即 $\operatorname{MSET}(\mathcal{A})$ 对应 OGF 的系数。经典做法是每种体积 $v$ 对应因子 $\frac{1}{1-x^v}$乘积的 $\ln$ 化加再整体做一次多项式 exp。例题无标号无根树计数洛谷 P5900题意求 $n$ 个节点的无标号无根树个数对 $998244353$ 取模$1\leq n\leq 2\times10^5$。解设无标号有根树类为 $\mathcal{T}$则$$ \mathcal{T}{\bullet}\times\operatorname{MSET}(\mathcal{T}) $$根据 Richard Otter 的论文The Number of Trees无根树的 OGF 为$$ T(z)-\frac{1}{2}T^2(z)\frac{1}{2}T(z^2) $$前几项系数为1 1 1 2 3 6 11 23 47 106忽略常数项即 OEIS A000055。Powerset 构造所有子集Powerset 构造生成所有子集$$ \operatorname{PSET}(\mathcal{A})\cong\prod_{\alpha\in\mathcal{A}}\left({\epsilon}{\alpha}\right) $$且要求 $\mathcal{A}_0\varnothing$。例$$ \begin{aligned} \operatorname{PSET}({a}){\epsilon}{a}\ \operatorname{PSET}({a,b}){\epsilon}{a}{b}{(a,b)}\ \operatorname{PSET}({a,b,c}){\epsilon}{a}{b}{(a,b)}{c}{(a,c)}{(b,c)}{(a,b,c)} \end{aligned} $$对应 OGF 为Pólya 指数·改$$ \overline{\operatorname{Exp}}(A(z))\prod_{\alpha\in\mathcal{A}}\left(1z^{\lvert\alpha\rvert}\right)\exp\left(\frac{A(z)}{1}-\frac{A(z^2)}{2}\frac{A(z^3)}{3}-\cdots\right) $$容易发现 $\operatorname{PSET}(\mathcal{A})\subset\operatorname{MSET}(\mathcal{A})$因为每个元素最多出现一次。Cycle 构造轮换等价Cycle 构造生成所有组合但不区分仅轮换不同的组合$$ \operatorname{CYC}(\mathcal{A})\left(\operatorname{SEQ}(\mathcal{A})\setminus{\epsilon}\right)/\mathbf{S} $$其中 $\mathbf{S}$ 为等价关系$(\alpha_1,\dots,\alpha_n)\mathbf{S}(\beta_1,\dots,\beta_n)$ 当且仅当存在循环移位 $\tau$ 使得对所有 $j$ 有 $\beta_j\alpha_{\tau(j)}$。例令 $\texttt{a},\texttt{b}$ 均为大小为 $1$ 的字符则大小为 $3$、$4$ 的轮换类分别为$$ \operatorname{CYC}({\texttt{a},\texttt{b}})_3{\texttt{aaa}}{\texttt{aab}}{\texttt{abb}}{\texttt{bbb}} $$其中 $\texttt{aab}\mathbf{S}\texttt{baa}\mathbf{S}\texttt{aba}$ 只保留其一$\texttt{abb}$ 同理而$$ \operatorname{CYC}({\texttt{a},\texttt{b}})_4{\texttt{aaaa}}{\texttt{aaab}}{\texttt{aabb}}{\texttt{abbb}}{\texttt{bbbb}}{\texttt{abab}} $$这里 $\texttt{abab}$ 轮换两次即回到自身是长度为 2 的周期串因此作为独立代表元出现。对应 OGF 为Pólya 对数$$ \operatorname{Log}(A(z))\sum_{n\geq 1}\frac{\varphi(n)}{n}\ln\frac{1}{1-A(z^n)} $$其中 $\varphi$ 为 Euler 函数。该构造的证明较复杂可参考 Flajolet 的论文The Cycle Construction或 Analytic Combinatorics 附录。从结构上可以看出 Cycle 构造在组合层面「少一个轮换自由度」因此其 OGF 由 Log 算子给出与 MSET 的 Exp 算子互为对偶。有限制的构造跟踪组成部分个数以上构造都未限制「组成部分」的个数。若想限制个数可在 $\operatorname{SEQ}$ 下标处给出一个作用于整数的谓词例如$$ \operatorname{SEQ}{k}(\mathcal{B}),\quad \operatorname{SEQ}{\geq k}(\mathcal{B}),\quad \operatorname{SEQ}_{1..k}(\mathcal{B}) $$其中 $\operatorname{SEQ}_{k}$ 常简写为 $\operatorname{SEQ}k$$\operatorname{SEQ}{1..k}$ 表示个数在区间 $[1..k]$ 上。令 $\mathfrak{K}$ 为上述 $\operatorname{SEQ},\operatorname{PSET},\operatorname{MSET},\operatorname{CYC}$ 之一考察$$ \mathcal{A}\mathfrak{K}_k(\mathcal{B}) $$设 $\chi$ 函数作用在组合对象上返回其组成部分个数即要求 $\chi(\alpha)k$。不妨增加一个一元 $u$ 来「跟踪」组成部分的个数$$ A(z,u)\sum_{n,k}A_{n,k}u^kz^n\sum_{\alpha\in\mathcal{A}}z^{\lvert\alpha\rvert}u^{\chi(\alpha)} $$其中 $A_{n,k}\operatorname{card}{\alpha\in\mathcal{A}\mid\lvert\alpha\rvertn,\chi(\alpha)k}$。提取 $[u^k]$ 即得到对应表达式。例如 $\mathcal{A}\operatorname{SEQ}_k(\mathcal{B})$$$ A(z,u)\sum_{k\geq 0}u^kB(z)^k\frac{1}{1-uB(z)} \implies A(z)B(z)^k $$显然也有$$ \mathcal{A}\operatorname{SEQ}_{\geq k}(\mathcal{B})\implies A(z)\frac{B(z)^k}{1-B(z)} $$对 $\operatorname{MSET}_k$ 与 $\operatorname{PSET}_k$有$$ A(z,u)\prod_n\left(1-uz^n\right)^{-b_n} \implies A(z)[u^k]\exp\left(\frac{u}{1}B(z)\frac{u^2}{2}B(z^2)\frac{u^3}{3}B(z^3)\cdots\right) $$和$$ A(z,u)\prod_n\left(1uz^n\right)^{b_n} \implies A(z)[u^k]\exp\left(\frac{u}{1}B(z)-\frac{u^2}{2}B(z^2)\frac{u^3}{3}B(z^3)-\cdots\right) $$对 $\operatorname{CYC}_k(\mathcal{B})$ 同理可推。关键观察$\mathcal{A}\mathfrak{K}_k(\mathcal{B})$ 中 $A(z)$ 是 $B(z),B(z^2),\dots,B(z^k)$ 的表达式——因此计算这类 OGF 只需求出 $B$ 的前若干次复合即可。另一个注意点是对于有限制构造 $\mathfrak{K}_k(\mathcal{B})$不要求 $\mathcal{B}_0\varnothing$与无限制构造的条件不同。手工提取 $[u^k]$ 的完整示范以 $\operatorname{MSET}_3(\mathcal{B})$ 为例展开 $\exp$ 到 $u^3$ 项$$ [u^3]\exp(\cdots)\frac{B(z)^3}{6}\frac{B(z)B(z^2)}{2}\frac{B(z)^3}{3} $$以 $\operatorname{MSET}_4(\mathcal{B})$ 为例$$ [u^4]\exp(\cdots)\frac{B(z)^4}{24}\frac{B(z)^2B(z^2)}{4}\frac{B(z)B(z^3)}{3}\frac{B(z^2)^2}{8}\frac{B(z^4)}{4} $$这些结果与下文「常用有限制构造速查表」中 MSET 列的公式完全一致可作为推导正确性的交叉验证。常用有限制构造速查表$$ \begin{aligned} \operatorname{PSET}{2}(\mathcal{A}):\quad \frac{A(z)^2}{2}-\frac{A(z^2)}{2}\ \operatorname{MSET}{2}(\mathcal{A}):\quad \frac{A(z)^2}{2}\frac{A(z^2)}{2}\ \operatorname{CYC}_{2}(\mathcal{A}):\quad \frac{A(z)^2}{2}\frac{A(z^2)}{2} \end{aligned} $$$$ \begin{aligned} \operatorname{PSET}{3}(\mathcal{A}):\quad \frac{A(z)^3}{6}-\frac{A(z)A(z^2)}{2}\frac{A(z^3)}{3}\ \operatorname{MSET}{3}(\mathcal{A}):\quad \frac{A(z)^3}{6}\frac{A(z)A(z^2)}{2}\frac{A(z^3)}{3}\ \operatorname{CYC}_{3}(\mathcal{A}):\quad \frac{A(z)^3}{3}\frac{2A(z^3)}{3} \end{aligned} $$$$ \begin{aligned} \operatorname{PSET}{4}(\mathcal{A}):\quad \frac{A(z)^4}{24}-\frac{A(z)^2A(z^2)}{4}\frac{A(z)A(z^3)}{3}\frac{A(z^2)^2}{8}-\frac{A(z^4)}{4}\ \operatorname{MSET}{4}(\mathcal{A}):\quad \frac{A(z)^4}{24}\frac{A(z)^2A(z^2)}{4}\frac{A(z)A(z^3)}{3}\frac{A(z^2)^2}{8}\frac{A(z^4)}{4}\ \operatorname{CYC}_{4}(\mathcal{A}):\quad \frac{A(z)^4}{4}\frac{A(z^2)^2}{4}\frac{A(z^4)}{2} \end{aligned} $$需要说明这类系数提取计算虽然有效但比较繁琐其一般化工具是Pólya 枚举定理PET与Cycle Index——后者在 OEIS 的生成函数表达式中也经常出现。OI 实现中若需在模 $998244353$ 下批量计算 $\operatorname{MSET}_k$常见的落地方式是「先多项式 ln → 加权求和 → 多项式 exp」与 docs/math/poly/elementary-func.md 中的 $\exp/\ln$ 算法直接对应。例题烷基计数LOJ 6538加强版 ×2题意求 $n$ 个节点的有根无序树的个数对 $998244353$ 取模要求根节点度数不超过 $3$、其余节点度数不超过 $4$。约定 $1\leq n\leq 10^5$。解设组合类为 $\mathcal{T}$则$$ \mathcal{T}{\bullet}\times\operatorname{MSET}_{0,1,2,3}(\mathcal{T}) $$其中 $\operatorname{MSET}_{0,1,2,3}$ 表示子树个数在 $0$ 到 $3$ 之间根节点至多 3 个子树。或令 $\hat{\mathcal{T}}\mathcal{T}{\epsilon}$则$$ \hat{\mathcal{T}}{\epsilon}{\bullet}\times\operatorname{MSET}_{3}(\hat{\mathcal{T}}) $$两种写法得到相同结果——前者直接限制根的度数为 $\leq 3$后者用空树 $\epsilon$ 吸收「没有该子树」的情况从而统一为恰好 $3$ 个「槽位」。这正是有限制构造在树计数中的经典应用。方法总结与实现落地将本方法总结为可操作的三步流程写出组合类方程把待计数对象用 $\mathcal{E},\mathcal{Z}$ 与五大构造并、积、SEQ、MSET、PSET、CYC组合表达需要限制部件个数时加上下标有限制构造翻译为生成函数方程按「并→加、积→乘、SEQ→$1/(1-A)$、MSET→$\exp(\sum A(z^k)/k)$、PSET→$\exp(\sum(-1)^{k-1}A(z^k)/k)$、CYC→$\operatorname{Log}$」的对应规则机械写出 OGF 方程求解并提取系数解方程如 $T(z)z/(1-T(z))$、用牛顿迭代求形式幂级数的逆/exp/lndocs/math/poly/newton.md、elementary-func.md再输出前 $n$ 项系数。该流程在 OI-wiki 仓库中有直接的可验证证据无标号图的枚举代码 graph-enumeration_1.cpp 先以「所有图」「所有欧拉图」「所有二分图」的生成函数为起点通过多项式ln得到「连通图」等计数再以exp还原这正是 Exp/Log 这对算子在符号化方法中的逆运算关系其配套题面与数据见 docs/math/examples/graph-enumeration 对应的 .in/.ans 对。在竞赛实战中本方法适用的前提是模数适合 NTT如 $998244353$见 docs/math/poly/ntt.md且需要实现多项式求逆、ln、exp 等基础运算若仅有 $\mathcal{O}(n^2)$ 的朴素卷积则只适合处理规模较小的用例例如速查表中 $k\leq 4$ 的有限制构造可直接按公式逐项计算。参考文献Philippe Flajolet and Robert Sedgewick.Analytic Combinatorics本文档即其第一章的无标号部分的简化。文中涉及的经典结论出处Otter,The Number of Trees无标号无根树 OGFFlajolet,The Cycle ConstructionCycle 构造 OGFPólya 枚举定理与 Cycle Index有限制构造的一般化工具。题面来源LOJ 6268 分拆数、洛谷 P4389 付公主的背包、洛谷 P5900 无标号无根树计数、LOJ 6538 烷基计数加强版 ×2。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考