自动搬运

查看原文

来自洛谷，原作者为

	9AC8E2 最低な人生で简単に终わるんだ

搬运于2025-08-24 22:22:18，当前版本为作者最后更新于2020-08-27 13:46:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

前置知识:烷基计数

烷烃计数

已知碳原子个数 $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}$$

$-1$ 是因为 $0$ 个点并不能被计入方案

$\sum s$

设答案的 $OGF$ 为 $S(x)$

$$S(x)=A(x^2)$$

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

代码