[WC2019] 数树 op=2 线性做法题解 & 闲话
NaCly_Fish
·
·
个人记录
题解
原题链接
对于给定的 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 反演：
\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 有标号荒漠计数、CF1439D INOI Final Contests、P10324 洞察（Insight） 等题目中用到，已经算是个经典技巧了。怎么现在才发出来？
可能是题目的年代有些久远（5 年已经算是久远了吗？），老选手们都忘了这个题，而新选手并未了解过上述做法，就导致这题一直没有 \text{op}=2 情形的 \Theta(n) 时间复杂度提交记录。
在考场上看到这种问题时，如果没有相关经验，第一反应肯定还是做多项式 \exp —— 虽然写起来麻烦，但容易想且确保有效。在题面给的数据范围比较小时，选手通常想到的都是复杂度较高的做法（比如 P10082 [GDKOI2024 提高组] 鸡 实际存在 \Theta(\log n) 复杂度的算法），因为够用就行。在考场上这样做完全没问题，但我希望各位闲下来的时候，也能稍微看看自己做过的题，想想这个复杂度是否真的达到了下界。这不仅是一种智力的练习，也是对固有思路的突破。
回头来总结一下这类做法的核心思想，就是对于幂级数 f(x)，已经知道其满足一个超越方程（如果是代数方程，那么 f(x) 就是代数的，其具有许多优良性质使得我们不必再使用此方法），可以尝试将 f'(x) 用 f(x) 来表示，这会有助于使用 Lagrange 反演等工具。
虽然已经多次使用过，但目前来看这种做法的局限性还比较大。我们一般需要得到 f^{(i)}(x) 的线性组合表示为 g(f(x)) 的形式，其中 g(x) 要求是一个代数幂级数。
这种做法应该如何扩展？我并未了解过相关资料，所以也不清楚。不过 EI 曾说过：「解决问题的方法是朴实的，甚至在问题被以正确的方式提出的时候，叙述本身就足以使人一步步走向结果。」其实有很多前人没想到的算法，都出人意料地简洁而优美（比如，\Theta(n \log^2 n) 的多项式复合）。这个做法目前还没一般化，大概还是因为没发现问题的本质吧。
愿我们的思维永不受限，一切难题终将迎刃而解。