自动搬运

查看原文

来自洛谷，原作者为

	Aleph1022 「笑可以天然地飘洒 心是一地草野 唯一的家乡」

搬运于2025-08-24 22:47:53，当前版本为作者最后更新于2024-01-05 11:34:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

抄一个 EI 做法。
其实我在赛场上就是这么想的，但是因为一些原因推错了，然后直到比赛结束也没改对……
痛失首杀（？）

经常用多元 Lagrange 反演的同学都知道，这个题很能多元 Lagrange 反演。用 $x, y$ 计量白、黑点，$W, B$ 计量根为白、黑点的树，立刻有方程

$$\begin{cases} W = x \exp(W+B) \\ B = y \exp W \end{cases} $$

然后考虑环。我们知道一个任意的环是

$$\ln \frac1{1-BW-W}$$

$B, W$ 均出现奇数次的情况是

$$\frac14\ln \frac{(1+BW)^2-W^2}{(1-BW)^2-W^2}$$

上式减下式再 $\exp$ 可得

$$\frac1{1-BW-W} \left(\frac{(1-BW)^2-W^2}{(1+BW)^2-W^2}\right)^{1/4} $$

我们要求其 $\left[\frac{x^ny^m}{n!m!}\right]$，施多元 Lagrange 反演得

$$\left[\frac{x^ny^m}{n!m!}\right]\left(\frac{(1-xy)^2-y^2}{(1+xy)^2-y^2}\right)^{1/4}\mathrm e^{(n+m)x+ny} $$

欲有 $O(nm)$ 做法，只需先求出 $\left(\frac{(1-xy)^2-y^2}{(1+xy)^2-y^2}\right)^{1/4}$ 的系数，且其微分方程是容易得到的。

记 $a_n(y) = \left[\frac{x^n}{n!}\right]\left(\frac{(1-xy)^2-y^2}{(1+xy)^2-y^2}\right)^{1/4}$，我们有递推式

$$\begin{aligned} a_n =& -ya_{n-1} \\ & +2(n-1)(n-2)(1+y^2) a_{n-2} \\ & -(n-1)(n-2)y(1-y^2) a_{n-3} \\ & -(n-1)(n-2)(n-3)(n-4)(1-y^2)^2 a_{n-4} \end{aligned} $$