题解 P6598 【烷烃计数】

· · 题解

感觉这题比烯烃计数难一点啊

前置知识:烷基计数

烷烃计数

已知碳原子个数 n，求对应的烷烃有多少种同分异构体

不考虑空间异构

题解

就是 n 个点的每个点的度数个数 \leq 4 的无标号无根树计数

参考博客

无标号无根数还是很难做,考虑怎么做成除根节点外每个点的子节点个数 \leq 3,根节点的子节点个数 \leq 4 的无标号有根树计数

考虑对于一棵无根树,设枚举一个点为关键点,整棵树的点等价类数为 p ,枚举一条边为关键边,整棵树的边等价类数为 q,设 s=1 当且仅当有两个重心且两个重心等价,那么有 p-q+s=1

s=0$ 时,考虑除重心外的每个点与其父亲边(以重心为根)的贡献.若两个点等价,那么这两个点的父亲边(以重心为根)也等价,所以除重心外的贡献为 $0

对于重心,它不可能与其他任何一个点等价,所以贡献为 1

s=1$ 时,因为两个重心等价,所以 $p-q=-1

这样,对于每棵无标号无根树用 p-q+s 统计答案即可做到不重不漏

对于 \sum p,\sum q,\sum s 分别统计答案

\sum p

枚举无标号无根树并统计点等价类,将每个点作为根,就相当于求无标号有根树

即相当于除根节点外每个点的子节点个数 \leq 3,根节点的子节点个数 \leq 4 的无标号有根树计数

除根外的节点的子节点个数 \leq3 ,即相当于前面做过的烷基计数

设烷基计数的 OGF 为 A(x)

对根节点再做一遍 Burnside,设 \sum p 的 OGF 为 P(x)

一共有 4!=24 种置换,分类讨论即可

p_{x+1}=\frac{\sum_{i_i+i_2+i_3+i_4=x}a_{i_1}a_{i_2}a_{i_3}a_{i_4}+6\sum_{2i_1+i_2+i_3=x}a_{i_1}a_{i_2}a_{i_3}+3\sum_{2i_1+2i_2=x}a_{i_1}a_{i_2}+8\sum_{3i_1+i_2=x}a_{i_1}a_{i_2}+6\sum_{4i_1=x}a_{i_1}}{24} 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}

\sum q

就是求两个无标号有根树的根连起来后的不同构方案数

设答案的 OGF 为 Q(x)

Q(x)=\frac{(A(x)-1)^2+A(x^2)-1}{2} #### $\sum s

设答案的 OGF 为 S(x)

S(x)=A(x^2)

那么答案就是 P(x)-Q(x)+S(x)

代码