题解：P6597 烯烃计数
Zi_Gao
·
·
题解
0x00 有机物
不会化学？没关系哦，我也不会。本人在化学月考和期中考试中分别获得了 37/100 和 61/100 的成绩。你只需要知道：
- 键：链接两个原子的东西，对应 OI 中的边。XY 键就是连接 X 原子和 Y 原子的键，可以同时链几根键，变成 XY 双键、三键等。
- 碳原子：必须要连 4 根键，不能连自己但是两个碳原子可以连多根键。
- 氢原子：只能连 1 根键。
- 烷烃：每个碳原子都连了 4 根键，所有的碳碳都是单键。实际上有环的也叫烷烃，但是这次我们只考虑链状烷烃，形态是 OI 里面的一棵树，那么烷烃的通式为 C_{n}H_{2n+2}。
- 烷基：去掉一个碳的一个氢原子，烷基的通式为 C_{n}H_{2n+1}。
- 烯烃：有一个碳碳双键，这两个碳原子又分别链接了两个烷基。
- 同分异构体：有相同分子式，但是结构不同的有机物，对应 OI 中的无标号树同构问题。
0x01 烷基计数
想一下去掉了一个氢原子的那个碳给我们带来了什么？答案是，把一个无根树变成一个有根树。我们把这个有机物从这个没连接的碳键拎起来，那么这个无根树就变成了每个非叶子点都链接了三个儿子。
设 F(x) 是答案的生成函数，考虑每次把三个儿子填进去的方案数，要考虑是否同构所以用 Burnside 引理。枚举 6 种置换：
-
-
-
全部加起来取平均数：
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}
得到答案。