题解 P5434 【【模板】有标号荒漠计数】
NaCly_Fish
·
·
题解
update on 2022.7.7：本题解全面更新，改为更优的做法，并给出一个比较清晰的推导。
题目要求「荒漠」的数量，而这个只是由若干个「无根仙人掌」连通块组成的。可以先求出有标号有根仙人掌的数量，并设其指数型生成函数（EGF）为 F(x)。
考虑有 i 个仙人掌的根连成一条链，方案的 EGF 自然是 F(x)^i。然后将这条链首尾分别与新根相连，对于 i=1 方案数仍然是 F(x)；但对于 i\geq 2，与根连接后就形成了环，但链有正反而环没有，故方案数为 F(x)^i/2。
新根可以按上述方式接若干互相无序的环（或点），由此可以得到方程：
F(x)=x\exp \left( F(x)+\frac 12\sum_{i\ge 2} F(x)^i\right)
化简即得
F(x)=x \exp \frac{2F(x)-F(x)^2}{2-2F(x)}
设有标号无根仙人掌数量的 EGF 为 G(x)。从无根变为有根就是从所有节点中随便钦定一个作根，故 F(x)=xG'(x)。
直接牛顿迭代提取 \exp G(x) 的系数可以做到 \Theta(n \log n) 的时间复杂度，但写起来比较复杂且不够优秀。
但这个形式还不便于我们进一步优化，有没有办法避开 G'(x)，直接建立 G(x) 和 F(x) 的关系呢？用一些组合意义的技巧可以求解，不过这里有一种（不知是否通用）的代数方法。
最理想的情况当然是 G(x)=H(F(x))，而且 H(x) 的形式最好比较简单。对两边求导后同乘 x 得
F(x)=xF'(x)H'(F(x))
设
B'(x)= \frac{2x-x^2}{2-2x}
（这里设出 B' 是因为后面还要用 B，写起来方便）则 F(x) 的方程就是
F(x)=x\exp B'(F(x))
求导得
F'(x)=\exp B'(F(x))+xB''(F(x))F'(x)\exp B'(F(x))
xF'(x)=F(x)+xB''(F(x))F'(x)F(x)
xF'(x)(1-B''(F(x))F(x))=F(x)
此时可以直接把 xF'(x) 替换为不含 F(x) 的项，即
\frac{F(x)}{H'(F(x))}(1-B''(F(x))F(x))=F(x)
发现了什么？把 F(x) 全都换元为 z 就可以求解了：
H'(z)=1-zB''(z)
确定一下常数项就可以得到
H(z)=z+B(z)-zB'(z)
障碍完美清除，现在就可以使用 Lagrange 反演：
[x^n]\text e^{H(F(x))}=\frac 1n [x^{n-1}]H'(x) \text e^{H(x)}\left(\frac{x}{F^{\langle -1 \rangle}(x)} \right)^n
这个式子有点长，我们分三部分来看。由 F(x) 的原方程可得
F^{\langle -1 \rangle}(x)= x \exp \frac{x^2-2x}{2-2x}
这个东西并不是代数的，但其特殊性质使得下式是微分有限的：
\left(\frac{x}{F^{\langle -1 \rangle}(x)}\right)^n = \exp n\frac{2x-x^2}{2-2x}
再分析 \text e^{H(x)}，用一点简单的高数知识可以求出
B(x)=\frac 14(-2x+x^2-2\ln(1-x))
再代入计算 \text e^{H(x)}：
\text e^{H(x)}=\text e^{x-xB'(x)}\exp\left({\frac{-2x+x^2}{4}}\right)\frac{1}{\sqrt{1-x}}
其中 B'(x) 是代数的，\text e^{x-xB'(x)} 是微分有限的，其余部分也微分有限，故 \text e^{H(x)} 微分有限。
最后 H'(x) 这一项就很简单了，它是代数的，显然也是微分有限的。
综上，提取 \text e^{H(F(x))} 的一项系数可以做到 \Theta(n) 或 \Theta(\sqrt n \log n) 的时间复杂度。具体如下：
设
f(x)=\exp\left((n-x)\frac{2x-x^2}{2-2x}+\frac{2x+x^2}{4} \right)
对两遍求导，可以化简出
2(1-x)^2f'(x)=((2n+1)-(2n+5)x+(n+4)x^2-x^3)f(x)
类似地设
g(x)= (1-x)^{-5/2}f(x)
可以得到
2(1-x)^2g'(x)=((2n+6)-(2n+10)x+(n+4)x^2-x^3)g(x)
这是一个四阶一次的整式递推，最后的答案就是：
ng(x)
看代码点这里
ps：本文有参考 Daniel13265 早期提供的题解，但推导方法上有许多不同。