旧神归来（Return of Them）题解

· · 题解

第 1 步：我们首先将问题进行第一步抽象：答案只和叶子的深度构成的多重集相关。

我们考虑进行一次操作之后对于度数集合的影响：原多重集为 S，将一个深度为 d 的节点进行替换之后，会生成一族深度为 S+d 的叶子，并且失去一个原先的深度为 d 的叶子。

第 2 步：将多重集写作 GF，观察形式。

设原来的多重集的 GF 为 S(x)，新生成的一组叶子就是 x^d S(x)，最后要删去一个深度为 d 的叶子，那么最后的集合就是 (1+x^d)S(x) - x^d。

第 3 步：猜想相邻两次替换操作交换不影响答案。

为了验证，我们尝试写出来接连替换两个深度分别为 d,e 的叶子会发生什么：

(1+x^e)[(1+x^d)S(x) - x^d] -x^e = (1+x^e)(1+x^d)S(x) - x^e -x^d - x^{d+e}

右式关于 d,e 对称，显然交换。并且右边的形式诱导我们写成更加漂亮的样子：

(1+x^e)(1+x^d) S(x) - (1+x^e)(1+x^d) + 1

第 4 步：

设深度为 i 的叶节点被替换了 a_i 次，前面的推导引导我们知道这样一个无穷序列能消去任何深度有限的叶子，当且仅当

(S(x)-1) \prod _{i\ge 1}(1+x^i)^{a_i} + 1 = 0

移项可得

\prod _{i\ge 1}(1+x^i)^{a_i} = (1-S(x))^{-1}

第 5 步：

对于左式这种变换我们已经很熟悉了，两边取对数，有

\sum_{i\ge 1} a_i \ln (1+x^i) = \ln \frac 1{1-S(x)}

也即

\sum_{ij=k} a_i \cdot \frac{(-1)^{j-1}}{j} = [x^k]\ln \frac 1{1-S(x)}

左式直接从小到大反解，复杂度为 \Theta(n\log n)，亦可根据各维独立性做到 \Theta(n\log\log n)。

右式可以做到 \Theta(n\log n)。

本问题在 $\Theta(n\log n)$ 内解决。