题解 P5564 【[Celeste-B]Say Goodbye】

· · 题解

在博客园食用更佳：https://www.cnblogs.com/PinkRabbit/p/11525881.html。

题意简述：

有 n 个点，染 m 种颜色，第 i 种颜色染恰好 cnt_i 个节点，满足 cnt_1+cnt_2+\cdots+cnt_m=n。

求这 n 个点组成的本质不同的无标号+有序（子树有序）基环（环长至少为 2）树个数。

两棵基环树本质相同当且仅当通过环的旋转（不能翻转）后能使得它们完全相同。

题解：

首先考虑只染一种颜色的 n 个点（n\ge1）的无标号有根有序树个数计数。
考虑这棵树的括号序，发现其括号序是长度为 n 的合法括号串，但是必须满足最外层括号（根节点）只有一对。
即 n 个点的有根有序树个数为 n-1 对括号组成的合法括号串，即第 n-1 个卡特兰数。
令 n 个点的有根有序树个数为 t_n，令其 OGF 为 \displaystyle T=\sum_{i=1}^{+\infty}t_ix^i，即 T=xC，其中 C 为卡特兰数的 OGF。

再考虑染色的问题，不难发现只要有序，则染色和树形态是相互独立的。
即只要乘上一个多重组合数 \displaystyle\binom{n}{cnt_1,cnt_2,\ldots,cnt_m} 即可。

回到原问题，枚举环长 k，使用 Burnside 引理统计等价类个数。环的旋转置换的统计方法是常见的，即枚举因数 d，等价于循环 d 格的置换个数为 \varphi\!\left(\dfrac{k}{d}\right)。则有：

\begin{aligned}\mathbf{Ans}&=\sum_{k=2}^{n}\dfrac{1}{k}\sum_{d|k}\varphi\!\left(\dfrac{k}{d}\right)\!\cdot f(d)\end{aligned}

其中 f(d) 表示循环 d 格时的不动点个数。

循环 d 格时，存在 d 个长度为 \dfrac{k}{d} 的循环，循环内的每个元素都代表一棵外向树。为了方便进一步的展开，交换 d 与 \dfrac{k}{d} 的意义，枚举 d 为循环长度，而 \dfrac{k}{d} 为循环个数。此时每个循环内的树形态相互独立，而且染色和树形态相互独立，但每个循环的树形态必须相同，且染色也必须相同，也就是说有 \dfrac{k}{d} 棵树，且总点数为 \dfrac{n}{d}，并且需要满足每种颜色的个数是 d 的倍数，即 \left.d\:\middle|\:\gcd\limits_{i=1}^{m}cnt_i\right.。则公式变为：

\begin{aligned}\mathbf{Ans}&=\sum_{k=2}^{n}\dfrac{1}{k}\sum_{d|k}\varphi(d)\cdot f\!\left(\dfrac{k}{d}\right)\!\\&=\sum_{k=2}^{n}\dfrac{1}{k}\sum_{d|k}\varphi(d)\cdot\!\left\{\!\left[d\:\middle|\:\gcd\limits_{i=1}^{m}cnt_i\right]\!\cdot\!\left[x^{n/d}\right]\!T^{k/d}\cdot\binom{n/d}{cnt_1/d,cnt_2/d,\ldots,cnt_m/d}\right\}\!\end{aligned}

此时有两条路可走，其一是留下生成函数 T 的形式不变，其二是考虑使用卡特兰数的性质。

先使用第一种做法，考虑交换求和顺序并改变求和指标 k 为 kd：

\begin{aligned}\mathbf{Ans}&=\sum_{k=2}^{n}\dfrac{1}{k}\sum_{d|k}\varphi(d)\cdot\!\left\{\!\left[d\:\middle|\:\gcd_{i=1}^{m}cnt_i\right]\!\cdot\!\left[x^{n/d}\right]\!T^{k/d}\cdot\binom{n/d}{cnt_1/d,cnt_2/d,\ldots,cnt_m/d}\right\}\!\\&=-t_n\binom{n}{cnt_{1\ldots m}}+\sum_{d\mid\gcd_{i=1}^{m}cnt_i}\varphi(d)\cdot\binom{n/d}{cnt_{1\ldots m}/d}\cdot\!\left[x^{n/d}\right]\!\sum_{k=1}^{n/d}\frac{T^k}{kd}\\&=-t_n\binom{n}{cnt_{1\ldots m}}+\sum_{d\mid\gcd_{i=1}^{m}cnt_i}\frac{\varphi(d)}{d}\cdot\binom{n/d}{cnt_{1\ldots m}/d}\cdot\!\left[x^{n/d}\right]\!\sum_{k=1}^{+\infty}\frac{T^k}{k}\\&=-t_n\binom{n}{cnt_{1\ldots m}}+\sum_{d\mid\gcd_{i=1}^{m}cnt_i}\frac{\varphi(d)}{d}\cdot\binom{n/d}{cnt_{1\ldots m}/d}\cdot\!\left[x^{n/d}\right]\!(-\ln(1-T))\end{aligned}

第二行的第一项是因为后面统计了 d=k=1 的情况，但是实际不需要，所以要减掉。
最后一行利用了 \ln 在 1 处展开的的泰勒级数：\displaystyle\ln(1-x)=-\sum_{i=1}^{+\infty}\frac{x^i}{i}。
先使用多项式对数函数计算出 -\ln(1-T)，按照此式直接计算即可。时间复杂度 \mathcal{O}(n\log n+\sigma_0(n)\cdot m)。

第二种做法是考虑卡特兰数和自身的 m 次卷积的第 n 项的通项。

有公式 \displaystyle[x^n]C^m=\binom{2n+m-1}{n}-\binom{2n+m-1}{n-1}，将此式代入可得：

\begin{aligned}\mathbf{Ans}&=\sum_{k=2}^{n}\dfrac{1}{k}\sum_{d|k}\varphi(d)\cdot\!\left\{\!\left[d\:\middle|\:\gcd\limits_{i=1}^{m}cnt_i\right]\!\cdot\!\left[x^{n/d}\right]\!T^{k/d}\cdot\binom{n/d}{cnt_1/d,cnt_2/d,\ldots,cnt_m/d}\right\}\!\\&=\sum_{k=2}^{n}\dfrac{1}{k}\sum_{d|k}\varphi(d)\cdot\!\left\{\!\left[d\:\middle|\:\gcd\limits_{i=1}^{m}cnt_i\right]\!\cdot\!\left(\binom{2n/d-k/d-1}{2n/d-2k/d}-\binom{2n/d-k/d-1}{2n/d-2k/d-1}\right)\!\cdot\binom{n/d}{cnt_{1\ldots m}/d}\right\}\!\\&=-t_n\binom{n}{cnt_{1\ldots m}}+\sum_{d\mid\gcd_{i=1}^{m}cnt_i}\frac{\varphi(d)}{d}\cdot\binom{n/d}{cnt_{1\ldots m}/d}\sum_{k=1}^{n/d}\frac{1}{k}\!\left(\binom{2n/d-k-1}{2n/d-2k}-\binom{2n/d-k-1}{2n/d-2k-1}\right)\!\end{aligned}

直接计算即可，复杂度 \mathcal{O}(\sigma_0(n)(n+m))。