2026.2 状态精炼

洛谷P5564 [Celeste-B] Say Goodbye
神（秘）题。
考虑 \(n\) 个点有根无标号子树有序的树的计数，可以发现这东西就是 \(C_{n-1}\)，\(C\) 表示卡特兰数，因为这棵树的括号序是一对大括号里面套上由 \(n-1\) 对括号形成的合法括号序列。记 \(F(x)=\sum\limits_{i\ge2}C_{i-1}x^i\)。
如果有染色，乘上 \(\binom{n}{a_1,\dots,a_k}\) 就行。
根据 Burnside 引理可以得到：

\[ans=\sum_{l=2}^{n}\frac{1}{l}\sum_{d=1}^{l}f(d) \]

其中 \(l\) 表示基环树的环长，\(f(d)\) 表示环转 \(d\) 次的不动点个数。
经过一些转化可以得到：

\[ans=\sum_{l=2}^{n}\frac{1}{l}\sum_{d\mid l}\varphi(\frac{l}{d})f(d) \]

一个可能不对的证明：
假设当前要求 \(f(k)\)，环长为 \(l\)。
对于一张点编号在 \(0\sim l-1\) 的图，\(i\) 向 \((i+k)\bmod l\) 连边，则有 \(\gcd(k,l)\) 个环，环长为 \(\frac{l}{\gcd(k,l)}\)。
可以发现，每个环中每个点的子树结构和染色都要一样，因此 \(f(k)\) 的取值只和 \(\gcd(k,l)\) 有关，所以有 \(f(k)=f(\gcd(k,l))\)
然后枚举一下 \(\gcd\) 就能转化到那个形式。
对于 \(l\) 的一个因子 \(d\)，可以发现 \(f(l/d)=\binom{n/d}{a_1/d,\dots,a_k/d}\times[x^{n/d}]F^{l/d}\)。
带回去，有：

\[\begin{aligned}& ans\\=& \sum_{l=2}^{n}\frac{1}{l}\sum_{d\mid l}\varphi(d)f(\frac{l}{d})\\=& \sum_{l=2}^{n}\frac{1}{l}\sum_{d\mid l}\varphi(d)\binom{n/d}{a_1/d,\dots,a_k/d}\times[x^{n/d}]F^{l/d}\\=& -ans(d=1)+\sum_{d=1}^{n}\varphi(d)\binom{n/d}{a_1/d,\dots,a_k/d}\times[x^{n/d}]\sum_{k=1}^{n/d}\frac{F^k}{kd} \end{aligned}\]

对于最右边那个 \(\sum\limits_{k=1}^{n/d}\frac{F^k}{kd}\)，把 \(d\) 拉出去，发现 \(k\) 的上界其实可以开到正无穷，然后变成了 \(-\ln(1-F)\)，其实就是泰勒展开一下。
然后套一个多项式板子就行了！