自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:10:42，当前版本为作者最后更新于2019-06-20 18:00:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

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 早期提供的题解，但推导方法上有许多不同。