洛谷6597 烯烃计数
Luogu 分析 首先求出烷基的 OGF $F(x)$，具体求解过程可以看这里。 考虑一个烯烃断掉双键后会构成一棵根的儿子数 $\leq 2$、其余节点的儿子数 $\leq 3$ 的树，我们考虑求出其 OGF $G(x)$。 根据 Burnside 引理可以得到 这里减 $1$ 是因为双键两端都必须有碳原子（双键显然不能连在氢原子上）。 依据上式直接计算即可。时间复杂度 $\mathcal...
Luogu 分析 首先求出烷基的 OGF $F(x)$，具体求解过程可以看这里。 考虑一个烯烃断掉双键后会构成一棵根的儿子数 $\leq 2$、其余节点的儿子数 $\leq 3$ 的树，我们考虑求出其 OGF $G(x)$。 根据 Burnside 引理可以得到 这里减 $1$ 是因为双键两端都必须有碳原子（双键显然不能连在氢原子上）。 依据上式直接计算即可。时间复杂度 $\mathcal...
LOJ 分析 要求的就是每个节点的儿子数都不超过 $3$ 的无标号有根树数。 设其 OGF 为 $F(x)$，考虑列出一个关于 $F(x)$ 的方程。 不妨规定 $[x^0]F(x) = 1$，那么可以看成每个节点的儿子数都恰好为 $3$。 直接得出 $F(x) = 1 + F(x) ^ 3$ 显然是错误的，因为我们同构的情况被重复计算了。 因此可以考虑 Burnside 引理。对于 $(1...