题解：P14454 [ICPC 2025 Xi'an R] Heart of Darkness

· · 题解

题解

首先考虑算出不限制异色节点之间连边的方案数，再减去异色边小于 k 的树的个数。
先考虑计算异色边数恰好为 k 的情况，枚举黑点的数量 i，可以得到其为

\sum_{i=1}^n \binom{n}{i}i^{i-2} (n-i)! [x^k y^{n-i}](\text e^{xT(y)})^i

其中形式元 x 计量异色边数，y 计量白点数，T(y) 是有标号有根树数量的 EGF。
那么异色边小于 k 的树的个数就是

S_k=n![y^n] \sum_{j=0}^{k-1} \frac{T(y)^j}{j!}\sum_{i=1}^\infty \frac{i^{i-2+j}}{i!}y^i

由此也容易得到 k \to \infty 时 S_k（即不限制异色边数的答案）为

n![y^n]\sum_{i=1}^\infty \frac{i^{i-2}}{i!}(y \text e^{T(y)})^i=n![y^n]\sum_{i=1}^\infty \frac{i^{i-2}}{i!}T(y)^i

然后使用另类 Lagrange 反演处理 S_k：

S_k=n![x^n] \text e^{nx}(1-x)\color{red}{\sum_{j=0}^{k-1}\frac{x^j}{j!} \sum_{i=1}^\infty \frac{i^{i-2+j}}{i!}(x\text e^{-x})^i}

设 a_m 为红色部分的 [x^m] 项系数，则对于 m\leq k 时，a_m 显然是 m^{m-2}/m!，下面就只讨论 m > k 的情况：

\begin{aligned}a_m &=\sum_{j=0}^{k-1}\frac{1}{j!}\sum_{i=1}^{m-j}\frac{i^{i-2+j}}{i!}[x^{m-j}](x \text e^{-x})^i \\ &=\sum_{j=0}^{k-1}\frac{1}{j!} \sum_{i=1}^{m-j} \frac{i^{m-2}}{i!} \times \frac{(-1)^{m-j-i}}{(m-j-i)!} \\ &=\sum_{j=0}^{k-1}\frac{1}{j!} \begin{Bmatrix} m-2 \\ m -j\end{Bmatrix}\end{aligned}

根据 Stirling 多项式的性质（P8561）可知，a_m 是关于 m 不超过 2(k-1) 次的多项式，也就是说其 GF 是一个分母为 (1-x)^{2k-1} 的有理分式。所以在计算出 a_k 的前 (2k-1) 项之后，就可以用一次卷积快速求出其 GF。

现在就有：

S_k=n![x^n] \frac{\text e^{nx}}{(1-x)^{2k-1}}P(x)

其中 P(x) 是一个 \Theta(k) 次多项式（可能比分母高 2 次以内），此时可以直接以 \Theta(n) 的时间复杂度计算 S_k。
具体地，简单求导可以得到 \text e^{nx}/(1-x)^{2k-1} 系数的整式递推式，这样就容易处理了。

总时间复杂度 \Theta(n+k^2)。做到这个复杂度需要线性筛出 f(i)=i^i 的函数值，但时间常数较大，朴素地使用快速幂也是可以通过的。

后话

此题得到 \Theta(n + k^2) 的复杂度做法后，总觉得不够优美，就试图找出更优的做法。可惜一直没有结果。

目前可以得到此问题的一些转化，如：

a_m=\frac{1}{(k-1)!}\sum_{i=0}^{k-3}k^i\begin{Bmatrix} m-i-3 \\ m-k\end{Bmatrix} (k-1)! a_{m+k} = \frac{1}{m!}\sum_{j=0}^m \binom mj (-1)^{m-j} \frac{(k+m)^{k-2}j^m-j^{m+k-2}}{m+k-j}

但这两个转化看起来都不是很有用... 该怎么办呢？