题解：P6598 烷烃计数

lailai0916 · 2026-05-31 22:30:21 · 题解

参考资料

• 多项式牛顿迭代 - OI Wiki
• Pólya enumeration theorem - Wikipedia
• Burnside's lemma - Wikipedia
• A000602 - OEIS

题意简述

求 n 个碳原子的烷烃的同分异构体数量，对 998244353 取模。

等价于求 n 个点、每个点度数 \le 4 的无标号无根树的个数。

烷基计数

烷基（Alkyl）是烷烃去掉一个氢原子得到的基团。从断键处把分子拎起来，失去氢的碳作根，它还能连 3 个碳，其余每个碳有一个父亲、至多 3 个儿子。于是烷基就是每个节点至多 3 个儿子的无标号有根树。

设 A(x)=\sum_{n\ge 0}a_nx^n，a_n 为 n 个碳的烷基数。令 a_0=1，对应空烷基，也就是一个氢原子。

根下挂一个大小 \le 3 的烷基可重集。A(x) 已含空元素，所以「恰好挂 3 个」等同于「挂 \le 3 个非空烷基」。对 S_3 用 Burnside 引理（Burnside's Lemma），循环型 (1,1,1)、(1,2)、(3) 各有 1,3,2 个置换：

这是关于 A(x) 的方程，用 牛顿迭代（Newton's Iteration）解。精度从 x^m 倍增到 x^{2m} 时，A(x^2)、A(x^3) 只用到更低次的系数，当成常数。设：

对 A 求形式导数：

代入 A\gets A-\dfrac{G(A)}{G'(A)} 化简：

数论变换（NTT）配上多项式求逆，O(n\log n) 即可求出 A(x)\bmod x^{n+1}。

烷烃计数

烷烃是度数 \le 4 的无标号无根树。无根树不好直接数，钦定重心为根，转成有根树再容斥。

对一棵无根树数三样东西：

• 每个点轮流作根，得到的本质不同有根树数，记为点等价类数 p；
• 每条边作根（两端各挂一棵有根树），得到的本质不同方案数，记为边等价类数 q；
• 树恰有两个重心、且两重心等价时 s=1，否则 s=0。

那么任意一棵无根树都满足 p-q+s=1。

对所有无根树求和，记 \sum p,\sum q,\sum s 的生成函数为 P(x),Q(x),S(x)。\sum(p-q+s) 就是无根树总数，于是答案是 [x^n]\big(P(x)-Q(x)+S(x)\big)。