[WC2019] 数树 op=2 线性做法题解 & 闲话

### 题解 [原题链接](https://www.luogu.com.cn/problem/P5206) 对于给定的 $y \neq 1$，我们希望计算的是 $$\frac{(1-y)^n}{y^4}n![x^n]\exp\left(\frac{n^2y}{1-y}\sum_{i\geq 1} \frac{i^i}{i!}x^i \right)$$ 怎么处理呢？我们知道**有标号有根树**的 EGF 是 $$T(x)=\sum_{i\geq 1}\frac{i^{i-1}}{i!}x^i$$ 根据其满足的方程 $T(x)=x \text e^{T(x)}$ 对等式两边求导就有 $$\begin{aligned}T'(x)&=\frac{T(x)}{x}+T(x)T'(x) \\ xT'(x)&= \frac{T(x)}{1-T(x)}\end{aligned}$$ 所以答案为 $$\frac{(1-y)^n}{y^4}n![x^n]\exp\left(\frac{n^2y}{1-y} \frac{T(x)}{1-T(x)} \right)$$ 然后使用[另类 Lagrange 反演](https://www.luogu.com/article/qqwukp35)： $$\frac{(1-y)^n}{y^4}n![x^n]\exp\left(\frac{n^2y}{1-y} \frac{x}{1-x} \right)(1-x)\text e^{nx}$$ 这样就很显然可以整式递推了，具体而言我们只需求出形如 $$[x^n]\exp \left(\frac{ax}{1-x}+bx \right)$$ 这样的式子，其递推式为 $$(n+1)f_{n+1}=(a+b+2n)f_n-(2b+n-1)f_{n-1}+bf_{n-2}$$ 这样就能做到 $\Theta(n)$ 或 $\Theta(\sqrt n \log n)$ 的时间复杂度了。 **** ### 闲话 看完上面的题解，你可能会觉得如此简单！而且类似的技巧还在 [P5434 有标号荒漠计数](https://www.luogu.com.cn/problem/P5434)、[CF1439D INOI Final Contests](https://www.luogu.com.cn/problem/CF1439D)、[P10324 洞察（Insight）](https://www.luogu.com.cn/problem/P10324) 等题目中用到，已经算是个经典技巧了。怎么现在才发出来？ 可能是题目的年代有些久远（5 年已经算是久远了吗？），老选手们都忘了这个题，而新选手并未了解过上述做法，就导致这题一直没有 $\text{op}=2$ 情形的 $\Theta(n)$ 时间复杂度提交记录。 在考场上看到这种问题时，如果没有相关经验，第一反应肯定还是做多项式 $\exp$ —— 虽然写起来麻烦，但容易想且确保有效。在题面给的数据范围比较小时，选手通常想到的都是复杂度较高的做法（比如 [P10082 [GDKOI2024 提高组] 鸡](https://www.luogu.com.cn/problem/P10082) 实际存在 $\Theta(\log n)$ 复杂度的算法），因为够用就行。在考场上这样做完全没问题，但我希望各位闲下来的时候，也能稍微看看自己做过的题，想想这个复杂度是否真的达到了下界。这不仅是一种智力的练习，也是对固有思路的突破。 回头来总结一下这类做法的核心思想，就是对于幂级数 $f(x)$，已经知道其满足一个超越方程（如果是代数方程，那么 $f(x)$ 就是代数的，其具有许多优良性质使得我们不必再使用此方法），可以尝试将 $f'(x)$ 用 $f(x)$ 来表示，这会有助于使用 Lagrange 反演等工具。 虽然已经多次使用过，但目前来看这种做法的局限性还比较大。我们一般需要得到 $f^{(i)}(x)$ 的线性组合表示为 $g(f(x))$ 的形式，其中 $g(x)$ 要求是一个代数幂级数。 这种做法应该如何扩展？我并未了解过相关资料，所以也不清楚。不过 EI [曾说过](https://www.luogu.com/article/2y1ji19k)：「解决问题的方法是朴实的，甚至在问题被以正确的方式提出的时候，叙述本身就足以使人一步步走向结果。」其实有很多前人没想到的算法，都出人意料地简洁而优美（比如，$\Theta(n \log^2 n)$ 的多项式复合）。这个做法目前还没一般化，大概还是因为没发现问题的本质吧。 愿我们的思维永不受限，一切难题终将迎刃而解。