Cayley + EGF + Stirling数 + 拉格朗日反演：ICPC2025西安H

Heart of Darkness - Problem - QOJ.ac

题目要求至少 $k$ 条异色边，我们转化为求恰好 $0,\dots,k-1$ 条异色边，然后用总方案去减。

Cayley 公式：

• $n$ 个点带标号无根树：$n^{n-2}$
• $n$ 个点带标号有根树：$n^{n-1}$

我们首先枚举 $i$ 个黑点，然后它们组成一棵无根树，方案为：

$$\sum_{i=1}^n\binom n i i ^{i-2}$$

现在我们考虑在上面挂白点

EGF :

$a\times b\to a+b \binom {a+b}a$

Definition : $A(x)=\sum_{n=0}^\infty a_n\cdot\dfrac {x_n}{n!}$

Then:

$$A(x)B(x)=\sum_{i=0}^{\infty}\left(\sum_{i=0}^n\binom n ia_i b_{n-i}\right)\dfrac{x^n}{n!}$$

我们定义 $T(y)$，其中 $[y^n]T(y)$ 表示 $n$ 个点有根树的方案：

$$T(y)=\sum_{t=1}^{\infty}t^{t-1}\frac {y^t}{t!}$$

我们假设枚举有 $z$ 条异色边，那样子就有 $z$ 棵树。

现在我们先求在一个黑点上挂 $z$ 棵树，它贡献到生成函数 $[x^z]$ 处：

$$\sum_{z=0}^\infty \frac{T^z(y)\cdot x^z}{z!}=e^{xT(y)}$$

之所以要除 $z!$，是因为树之间没有差别。根据泰勒展开，上式为 $e^{xT(y)}$

而我们现在有 $i$ 黑点，因此方案为：$(e^{xT(y)})^i$，重新展开得到：

$$\sum_{z=0}^\infty \frac{T^z(y)i^z\cdot x^z}{z!}$$

现在我们本质上其实就是求这个东西：

$$\sum_{j=0}^{k-1}\sum_{i=1}^n\binom n i i ^{i-2}(n-i)![x^jy^{n-i}]\sum_{z=0}^\infty \frac{T^z(y)i^z\cdot x^z}{z!}$$

• $j$ 枚举的是总共 $j$ 条异色边
• 之所以乘 $(n-i)!$，是因为我们EGF要还原系数
• 前面 $i$ 个黑点，所以我们需要 $n-i$ 个白点，因此 $y$ 的次数为 $n-i$

变形一下：

$$\sum_{j=0}^{k-1}[y^{n-i}]\dfrac{i^jT^j(y)}{j!}\sum_{i=1}^n\binom n i (n-i)!i^{i-2}$$

显然，我们可以对黑点也用 $[y^i]$ 表示，那样子我们就可以直接在最外面提取 $[y^n]$ 了：

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

接下来我们来看看 $T(y)$ 的另一种表示方式，注意 $T(y)$ 是生成函数。显然 $T(y)$ 肯定要有一个根节点，而下面可以连任意多个子树，因此有：

$$T(y)=y\sum_{i=0}^{\infty}\frac{T^i(y)}{i!}=ye^{T(y)}$$

我们现在有一个关于 $T(y)$ 的函数：$T(y)=ye^{T(y)}$

拉格朗日反演：

假设已知 $y=f(x)$，我们现在想求其反函数 $x=g(y)$ 的泰勒展开。

对于 $y=f(x)$，我们必然可以写成：$y=\dfrac x {\phi(x)}$，这个时候我们有：

$$[y^n]g(y)=\frac 1 n[x^{n-1}]\phi^n(x)$$

另类拉格朗日反演：

如果我们要求的是复合函数，我们有：

$$[y^n]F(T(y))=[x^n]F(x)\phi^n(x)\left(1-x\frac{\phi'(x)}{\phi(x)}\right)$$

我们现在回过来看：$T(y)=ye^{T(y)}$，我们令 $x=T(y)$，则 $y=xe^{-x}$

根据定义有 $\phi(x)=e^x$，因此 $\phi^n(x)=e^{nx}$，$\phi'(x)=e^x$

我们回到我们最开始想求的式子，我们直接让包括 $T(y)$ 的这一大坨为 ：

$$F(T(y))=\sum_{j=0}^{k-1}\dfrac{T^j(y)}{j!}\sum_{i=1}^n\frac{i^{i+j-2}}{i!}y^i$$

而我们现在恰恰就是要求 $[y^n]F(T(y))$，直接套公式：

$$n![y^n]F(T(y))=n![x^n]e^{nx}(1-x)\sum_{j=0}^{k-1}\frac{x^j}{j!}\sum_{i=1}^n \frac{i^{i-2+j}}{i!}(xe^{-x})^i$$

令 $A(x)=\sum_{j=0}^{k-1}\frac{x^j}{j!}\sum_{i=1}^n \frac{i^{i-2+j}}{i!}(xe^{-x})^i$ ，令 $A(x)$ 的系数 $a_m=[x^m]A(x)$

在 $m$ 固定的，显然我们可以知道我们要取 $e^{-xi}$ 的哪一项，先泰勒展开：

$$e^{-xi}=\sum_{l=0}^{\infty}\frac{(-i)^lx^l}{l!}$$

显然 $l=m-i-j$，原式变为：

$$a_m=\sum_{j=0}^{k-1}\frac 1 {j!}\sum_{i=1}^n\frac{i^{i-2+j}}{i!}\cdot\frac{(-i)^{m-i-j}}{(m-i-j)!}$$

进一步化简和变形，得到：

$$a_m=\sum_{j=0}^{k-1}\frac 1{j!}\cdot\frac 1{(m-j)!}\sum_{i=1}^{m-j}(-1)^{m-j-i}\binom {m-j} i i^{m-2}$$

第二类Stirling数：

$$\begin{Bmatrix} n \\ k \end{Bmatrix} = \frac 1 {k!}\sum_{i=0}^k(-1)^{k-i}\binom k i i^n$$

因此上式可以直接变为：

$$a_m=\sum_{j=0}^{k-1}\frac 1{j!}\begin{Bmatrix}m-2 \\ m-j\end{Bmatrix}$$

第二类Stirling数的性质：

对于 $\begin{Bmatrix}m-2 \\ m-j\end{Bmatrix}$ ，当 $j$ 固定时，这是一个关于 $m$ 的不超过 $2j$ 次的多项式

因此多个斯特林数求和，得到的 $A(x)$ 也是一个关于 $m$，次数不超过 $2(k-1)$ 的多项式。

若 $A(x)$ 为 $d$ 次多项式，则其OGF的分母为 $(1-x)^{d+1}$

因此我们可以表示为：

$$A(x)=\frac{P(x)}{(1-x)^{2k-1}}$$

其中 $P(x)$ 是 $O(k)$ 级别的，我们要求的最终式子变为：

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

我们考虑 $P(x)$ 的计算：

$$P(x)=A(x)(1-x)^{2k-1}$$

而 $P(x)$ 是 $O(k)$ 级别的，所以我们可以用 $O(k^2)$ 算出 $A(x)$ 的前 $k$ 项，然后和 $(1-x)^{2k-1}$ 卷积即可。

$$\begin{Bmatrix} n \\ k \end{Bmatrix}=k\begin{Bmatrix} n-1 \\ k \end{Bmatrix}+\begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}$$

第二类Stirling数我们可以递推预处理，因此 $a_m$ 我们就可以 $O(k)$ 求出来了。

现在，我们就暴力枚举 $P(x)$ 中的每一项 $p_i$：

$$n!\sum_{i=0}^{2k}p_i[x^{n-i}]\frac{e^{nx}}{(1-x)^{2k-2}}$$

我们看后面这个，我们令其系数为 $c_m$，我们现在想快速求 $c_{n-i}$，令：

$$C(x)=\sum_{m=0}^{\infty}c_m x^m=\frac {e^{nx}}{(1-x)^r}$$

求导：

$$\begin{align*} C'(x)&=\sum_{m=1}^{\infty}c_{m}mx^{m-1}\\[11px] &=\frac{nxe^{nx}(1-x)^r-e^{nx}r(1-x)^{r-1}(-1)}{(1-x)^{2r}}\\[9px] &=\frac{e^{nx}}{(1-x)^r}\cdot\frac{n(1-x)+r}{1-x}\\[9px] &=\frac{n+r-nx}{1-x}C(x) \end{align*}$$

因此有：

$$(1-x)C'(x)=(n+r-nx)C(x)$$

左式：

$$(1-x)\sum_{m=1}^{\infty}c_{m}mx^{m-1}=\sum_{m=1}^{\infty}c_{m}mx^{m-1}-\sum_{m=1}^{\infty}c_{m}mx^{m}$$

右式：

$$(n+r)\sum_{m=0}^{\infty}c_m x^m-n\sum_{m=0}^{\infty}c_m x^{m+1}$$

我们提取 $x^{m-1}$ 的系数：

$$mc_m-(m-1)c_{m-1}=(n+r)c_{m-1}-nc_{m-2}$$

变形得到：

$$c_m=\frac{n+r+m-1}{m}c_{m-1}-\frac n m c_{m-2}$$

因此我们就可以用 $O(n)$ 的时间把 $c_m$ 递推出来了

总时间复杂度 $O(k^2+n)$