Skip to main content

__debug's Home Keep it simple, stupid

计算烷烃的同分异构体个数 II

我来填坑了! 搬运题面题解中…

\(O(n^2)\) 的方法: 传送门

题目描述

请你快速计算化学式为 \(\mathrm{C_nH_{2n + 2}}\) 的烷烃的同分异构体个数.

多组数据. 答案对 \(998244353\) 取模.

\(T, n \le 10^5\)

题解

\(T = 1, n \le 10^5\) 时的做法

先算烷基, 即有根树并且根的度数 \(\le 3\).

设 \(A(x)\) 为烷基的个数的生成函数. 根据 Pólya 定理, 我们有 $$A(x) = 1 + x \frac{A(x)^3 + 3A(x)A(x^2) + 2A(x^3)}{6}$$

这个可以用分治 FFT \(O(n \log^2 n)\) 解, 需要用到一些技巧. (听 yyt 说可以牛顿迭代)

同样地, 我们可以再次运用重心方法和 Pólya 定理算出烷烃的个数.

完整做法

考虑烷烃个数的生成函数 \(B(x)\). 但是并不方便直接用 \(A(x)\) 表示出 \(B(x)\).

对于一棵无根树, 令 \(p\) 和 \(q\) 分别表示这棵树的 点等价类 个数和 边等价类 个数. 定义 对称边 为满足连接的两个点是等价的的边 (显然这种边最多只有 1 条). 令 \(s\) 表示对称边的个数.

那么有下面这个式子恒成立: $$p - q + s = 1$$

证明十分简单. \(s = 0\) 时, 选任意一个重心做根, 容易证明没有其它点与这个根等价; 然后再考虑每个点及其父边的贡献即可. \(s = 1\) 时的情况还更简单一些.

有了这个式子, 接下来的事情就好办了. 对于所有 \(n\) 个点的烷烃, 有: $$\sum p - \sum q + \sum s = \sum 1$$

右边就是我们要求的.

令 \(P(x)\) 表示烷烃的 \(\sum p\) 的生成函数. 对于一个无根树, 选 \(n\) 个点中的任意一个点做根形成互不同构的的有根树的数量就是 \(p\).

用一下 Pólya 定理, 我们有 $$P(x) = x \frac{A(x^4) + 3A(x^2)^2 + 6A(x)^2A(x^2) + 8A(x)A(x^3) + 6A(x^4)}{24}$$

再令 \(Q(x)\) 表示烷烃的 \(\sum q\) 的生成函数. 对于一个无根树, 选 \(n - 1\) 条边中的任意一条边劈开, 插入一个度数为 2 的点形成的互不同构的有根树的数量就是 \(q\).

类似地, 我们有 $$Q(x) = \frac{\left(A(x)-1\right)^2 + \left(A(x^2) - 1\right)}{2}$$

然后显然 \(\sum s\) 的生成函数就是 \(A(x^2)\).

所以最终烷烃的数量的生成函数为 $$B(x) = P(x) - Q(x) + A(x^2)$$

时间复杂度为 \(O(n \log^2 n + T)\).

后记

相信每个 OIer 在学到同分异构体的时候都有一种把这题艹了的冲动. 于是我到处查查查终于发现了那个好用的结论.

甩链接跑: http://oeis.org/A000598/a000598.pdf

Comments

Comments powered by Disqus