P6597 烯烃计数 题解

0x00 有机物

不会化学？没关系你只需要知道：

1. 键：链接两个原子的东西，对应 OI 中的边。XY 键就是连接 X 原子和 Y 原子的键，可以同时链几根键，变成 XY 双键、三键等。
2. 碳原子：必须要连 4 根键，不能连自己但是两个碳原子可以连多根键。
3. 氢原子：只能连 1 根键。
4. 烷烃：每个碳原子都连了 4 根键，所有的碳碳都是单键。实际上有环的也叫烷烃，但是这次我们只考虑链状烷烃，形态是 OI 里面的一棵树，那么烷烃的通式为 $C_{n}H_{2n+2}$。
5. 烷基：去掉一个碳的一个氢原子，烷基的通式为 $C_{n}H_{2n+1}$。
6. 烯烃：有一个碳碳双键，这两个碳原子又分别链接了两个烷基。
7. 同分异构体：有相同分子式，但是结构不同的有机物，对应 OI 中的无标号树同构问题。

0x01 烷基计数

想一下去掉了一个氢原子的那个碳给我们带来了什么？答案是，把一个无根树变成一个有根树。我们把这个有机物从这个没连接的碳键拎起来，那么这个无根树就变成了每个非叶子点都链接了三个儿子。

设 $F(x)$ 是答案的生成函数，考虑每次把三个儿子填进去的方案数，要考虑是否同构所以用 Burnside 引理。枚举 6 种置换：

1. $(1,2,3)$：三个置换环，三个都任意，答案 $xF^3(x)+1$。
2. $(1,3,2),(2,1,3),(3,2,1)$：有两个儿子相同，一个任意，答案 $3(xF(x^2)F(x)+1)$。
3. $(2,3,1),(3,1,2)$：三个都相同，答案 $2(xF(x^3)+1)$。

全部加起来取平均数：

$$F(x)=\frac{x}{6}(F^3(x)+3F(x^2)F(x)+2F(x^3))+1$$

使用牛顿迭代求解，首先令

$$G(x,F(x))=F(x)-\frac{x}{6}(F^3(x)+3F(x^2)F(x)+2F(x^3))-1$$

那么已知 $G(x,F(x))\equiv 0 \pmod{x^n}$，那么可知：

$$F_1=F(x)-\frac{G(x,F(x))}{\frac{\partial G}{\partial F(x)}G(x,F(x))} \bmod{x^{2n}}$$

注意这里的求导是形势求导，把 $F(x)$ 当做变量求导，$F(x^2),F(x^3)$ 都当做常量，整理一下：

$$\begin{align} F_1&=F(x)-\frac{F(x)-\frac{x}{6}(F^3(x)+3F(x^2)F(x)+2F(x^3))-1}{1-\frac{x}{6}(3F^2(x)+3F(x^2))}\\ &=\frac{F(x)-\frac{x}{6}(3F^3(x)+3F(x^2)F(x))-F(x)+\frac{x}{6}(F^3(x)+3F(x^2)F(x)+2F(x^3))+1}{1-\frac{x}{6}(3F^2(x)+3F(x^2))}\\ &=\frac{1-\frac{x}{3}(F^3(x)-F(x^3))}{1-\frac{x}{2}(F^2(x)+F(x^2))} \end{align}$$

倍增迭代即可得到烷基计数的生成函数，我们记为 $A(x)$。

0x02 烯烃计数

从碳碳双键的地方把这个有机物拎起来，那么这两个碳原子再链接两个烷基就行，先用 Burnside 引理对一个碳原子进行计数：

$$F(x)=x\frac{A^2(x)+A(x^2)}{2}$$

继续用 Burnside 引理对两个碳原子进行计数：

$$G(x)=\frac{F^2(x)+F(x^2)}{2}$$

得到答案。