阴阳阵
Aleph1022
·
·
题解
抄一个 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}
$$
\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}
$$