P6598 烷烃计数 题解

· · 题解

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 种置换：

全部加起来取平均数：

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^3(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}

得到答案。

0x03 烷烃基数

把重心钦定为根变成一个有根树。实际上这里已经可以通过容斥方法，暴力卷一个式子来做了，但是这样太不优雅了，而且不能求出烷烃计数的生成函数。

烷烃是无根树怎么办，考虑把未知化为已知，强制钦定某一个点为根，那么就只需要考虑树上点的等价类就行，而点等价类就是有根数的计数，然后发现重心这个点很特殊，分类讨论一下：

  1. 只有一个重心：首先重心不与其他任何一个点等价，那么两个点等价意味着两个点的父亲边（以重心为根）等价，因为以这个点为根的有根树，到大小大于 \frac{n}{2} 儿子的边是唯一的。设点等价类数量为 p，边等价类数量为 q，那么 p-q=1。
  2. 有两个重心，两个重心不等价：同理可得 p-q=1。
  3. 两个重心等价：p-q=0。

那么对于一棵树计算 p,q,s，当有两个重心，且两个重心等价时 s=1，否则 s=0，对于任意一棵树有 p-q+s=1 恒等式。对三个部分分别生成函数 P,Q,S。

点等价就是根上加 4 个烷基儿子，使用 Burnside 引理进行计数 P(x)：

P(x)=x\frac{A^4(x)+6A(x^2)A^2(x)+3A(x^2)^2+8A(x^3)A(x)+6A(x^4)}{24}

边等价就是两个烷基连起来，并且不能是单个氢原子，继续 Burnside：

Q(x)=\frac{(A(x)-1)^2+A(x^2)-1}{2}

然后是重心等价，就是相同的两个烷基连起来：

S(x)=A(x^2)

那么 P-Q+S 就是烷烃计数的生成函数。