题解：P10324 洞察（Insight）
Aleph1022
·
·
题解
首先要注意到我们只要数树。进一步，删掉红色的点和相邻的边之后只剩下一片森林。
设 x, y 计量白点 / 黑点，W(x, y), B(x, y) 分别表示以白点 / 黑点为根的树的二元 EGF，可以列出方程
\begin{cases}
W(x, y) = x \mathrm e^{B(x, y)} \\
B(x, y) = y \mathrm e^{W(x, y)}
\end{cases}
对于 \mathrm{type}=0，我们只需计算
\left[\frac{x^ny^n}{n!n!}\right] \mathrm e^{W(x,y)+B(x,y)}
施多元 Lagrange 反演，可得其
\begin{aligned}
&=\left[\frac{x^ny^n}{n!n!}\right] \mathrm e^{(n+1)(x+y)}(1-xy) \\
&=(n+1)^{2n}-n^2(n+1)^{2n-2} \\
&=(2n+1)(n+1)^{2n-2}
\end{aligned}
对于 \mathrm{type}=1，我们需要计算
\left[\frac{x^ny^n}{n!n!}\right] \exp\left((x\partial_x+y\partial_y)(W+B)\right)
不妨在方程两侧取 \partial_x，可得
\begin{cases}
\partial_x W = \mathrm e^{B} + W \partial_x B\\
\partial_x B = B \partial_x W
\end{cases}
即
\begin{cases}
x\partial_x W = \frac W{1-WB} \\
x\partial_x B = \frac{WB}{1-WB}
\end{cases}
$$
\left[\frac{x^ny^n}{n!n!}\right] \exp\left(\frac{W+B+2WB}{1-WB}\right)
$$
施多元 Lagrange 反演知其
$$
=\left[\frac{x^ny^n}{n!n!}\right] \exp\left(\frac{x+y+2xy}{1-xy}\right) \mathrm e^{n(x+y)}(1-xy)
$$
换元，令 $x\mapsto st^{-1}, y\mapsto t$，可得其
$$
\begin{aligned}
&= n!^2 [s^n t^0]\exp\left(\frac{st^{-1}+t+2s}{1-s}\right) \mathrm e^{n(st^{-1}+t)}(1-s) \\
&= n!^2 [s^n t^0] \exp\left(\frac{(1+n(1-s))(st^{-1}+t)}{1-s}\right) \mathrm e^{\frac{2s}{1-s}} (1-s) \\
&= n!^2 [s^n] (1-s) \mathrm e^{\frac{2s}{1-s}} \sum_{j\ge 0} \frac1{j!^2} \left(\frac{1+n(1-s)}{1-s}\right)^{2j} s^j \\
&= n!^2 [s^n] (1-s) \mathrm e^{\frac{2s}{1-s}} {}_0F_1\left(;1;\frac{s(1+n(1-s))^2}{(1-s)^2}\right)
\end{aligned}
$$
是 D-Finite 的。时间复杂度 $O(n)$ 或 $O(\sqrt n \log n)$。