自动搬运

查看原文

来自洛谷，原作者为

	ftiasch 这个学院最强大的女孩子的朋友

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

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

以下是正文

---

ZJOI 2018 - 树

考虑一颗 $n$ 个节点的随机有根树 $T$，其中节点 $i$ ($2 \leq i \leq n$) 的父亲在 $\{1, \dots, i - 1\}$ 中均匀随机。

给定 $n$, $k$，求 $k$ 颗树 $T_1, \dots, T_k$ 两两同构的概率。

• $n \leq 2000$
• $k \leq 10^9$

解法

转化为递归构造

设 $\mathcal{T}_n$ 是所有 $n$ 个节点的无标号的有根树的集合，$\mathcal{T}_n = \{T_{n, 1}, \dots, T_{n, |\mathcal{T}_n|}\}$, $\mathcal{T} = \bigcup_{n \geq 0} \mathcal{T}_n$.

另外有函数 $s' : \mathcal{T} \to \mathbb{N}$. $s'(T)$ 表示用 $1, \dots, |T|$ 给点标号，保证节点标号大于父亲标号的方案数。

例子: $\mathcal{T}_4 = \{T_{4, 1}, T_{4, 2}, T_{t, 3}, T_{4, 4}\}$

$s'(T_{4, 1}) = 1$, $s'(T_{4, 2}) = 1$, $s'(T_{4, 3}) = 3$, $s'(T_{4, 3}) = 1$

可以验证 $s'(T_{4, 1}) + s'(T_{4, 2}) + s'(T_{4, 3}) + s'(T_{4, 4}) = 6 = 3!$.

---

所求就是

$$\frac{1}{[(n - 1)!]^k} \sum_{T \in \mathcal{T}_n} (s'(T))^k = n^k \sum_{T \in \mathcal{T}_n} \left(\frac{s'(T)}{|T|!}\right)^k. $$

根据递归构造，尝试枚举 $\mathcal{T}_n$ 中的树中的子树。设其中 $T_{i, j}$ 有 $x_{i, j}$ 颗。则

$$\sum_{T \in \mathcal{T}_n}s'(T) = (|T| - 1)! \prod_{\sum_{i, j} i x_{i, j} = n - 1} \left(\frac{s'(T_{i, j})}{|T_{i, j}|!}\right)^{x_{i,j}} \frac{1}{x_{i, j}!}. $$

这里可以注意到 $i x_{i, j} \leq n - 1$. 写成生成函数的形式就是

$$\sum_{T \in \mathcal{T}_n } s(T) = \frac{1}{|T|^k} [z^{n - 1}] \prod_{T' \in \mathcal{T}} \sum_{j \geq 0} \frac{(s(T') z^{|T'|})^j}{(j!)^k} = \frac{[z^{n - 1}]}{|T|^k} \prod_{i \geq 1} \prod_{T_i \in \mathcal{T}_i} \left(\sum_{j \geq 0} \frac{(s(T_i) z^i)^j}{(j!)^k} \right). $$

其中 $s(T) = \left(\frac{s'(T)}{|T|!}\right)^k$.

---

单独观察其中一项

$$\prod_{T_i \in \mathcal{T}_i} \left(\sum_{j \geq 0} \frac{(s(T_i) z^i)^j}{(j!)^k}\right). $$

从递推的角度，仿佛需要知道 $s(T_{i, 1}), \dots, s(T_{i, |T_i|})$ 的具体值才可以计算。

下面介绍一些理论依据。

对称多项式

设有 $n$ 个变量 $x_1, \dots, x_n$. 定义它们的 $k$-次幂和

$$p_k = \sum_{i = 1}^n x_i^k.$$

定义它们的 $k$-次初等对称多项式（Elementary Symmetric Polynomial）

$$e_k = \sum_{1\leq i_1 < \dots < i_k \leq n} x_{i_1} \dots x_{i_k}. $$

例子

$n = 4$ 时，

$$e_3 = x_1x_2x_3 + x_1x_2x_4 + x_1x_3x_4 + x_2x_3x_4. $$

---

牛顿恒等式 指出

$$k e_k = \sum_{i = 1}^k (-1)^{i - 1} e_{k - i} p_i. $$

如果定义它们的 $k$-次完全齐次多项式（Complete Homogeneous Symmetric Polynomials）

$$h_k = \sum_{1\leq i_1 \leq \dots \leq i_k \leq n} x_{i_1} \dots x_{i_k}. $$

同样有

$$k h_k = \sum_{i = 1} h_{k - i} p_i.$$

牛顿恒等式的生成函数证明

首先，

$$p_k = [z^k] \sum_{i = 1}^n \frac{1}{1 - x_i z} = [z^k] \sum_{i = 1}^{n} \sum_{j \geq 0} x_i^j z^j = [z^k] P(z). $$

其次，

$$e_k = [z^k] \prod_{i = 1}^n (1 + x_i z) = [z^k] E(z). $$

为了联系求和和求积，取对数有

$$\frac{E'(z)}{E(z)} = \frac{\mathrm{d}}{\mathrm{d} z}\, \ln E(z) = \sum_{i = 1}^n \frac{\mathrm{d}}{\mathrm{d} z}\, \ln(1 + x_i z) = \sum_{i = 1}^n \frac{x_i}{1 + x_i z} = \sum_{i = 1}^n \sum_{j \geq 0} (-1)^j x_i^{j + 1} z^j = \sum_{j \geq 0} (-1)^j p_{j + 1} z^j = Q(z). $$

---

比较 $[z^{k - 1}] E'(z) = [z^{k - 1}]E(z) Q(z)$ 有

$$k e_k = \sum_{j = 0}^{k - 1} (-1)^j e_{k - 1 - j} p_{j + 1} = \sum_{j = 1}^{k} (-1)^{j - 1} e_{k - j} p_j. $$

---

一个多项式 $f(x_1, \dots, x_n) \in R[x_1, \dots, x_n]$ 是对称多项式，当且仅当对于任意 $\{1, \dots, n\}$ 的排列 $\sigma_1, \dots, \sigma_n$，有

$$f(x_1, \dots, x_n) = f(x_{\sigma_1}, \dots, x_{\sigma_n}). $$

例子

$f(a, b, c) = a^2 b + b^2 c + c^2 a + ab^2 + bc^2 + ca^2$ 是对称多项式。

而 $g(a, b, c) = a^2 b + b^2 c + c^2 a$ 不是对称多项式，因为 $g(a, c, b) = a^2 c + c^2 b + b^2 a \neq g(a, b, c)$.

对称多项式基本定理

对称多项式基本定理指出，任意 $n$ 元 $m$ 次对称多项式可以用 $e_1, \dots, e_m$ 表示。等价地，用 $p_1, \dots, p_m$ 表示。

---

抽象地说，考虑 $n$ 元对称多项式环 $R[x_1, \dots, x_n]^{S_n}$.

对于任意 $f \in R[x_1, \dots, x_n]^{S_n}$, 存在多项式 $g \in R[x_1, \dots, x_n]$ 满足

$$f(x_1, \dots, x_n) = g(p_1, \dots, p_n).$$

例子：牛顿恒等式和贝尔多项式 #TODO

解法（续）

回到所求

$$\sum_{T \in \mathcal{T}_n} s(T) = \frac{[z^{n - 1}]}{|T|^k} \prod_{i \geq 1} \prod_{T_i \in \mathcal{T}_i} \left(\sum_{j \geq 0} \frac{(s(T_i) z^i)^j}{(j!)^k}\right). $$

如果令

$$\mathrm{FOREST}_{i}(z) = \prod_{T_i \in \mathcal{T}_i}\left(\sum_{j \geq 0} \frac{(s(T_i) z)^j}{(j!)^k}\right) = \sum_{j \geq 0} \mathrm{forest}_{i, j} z^{j}. $$

则

$$\sum_{T \in \mathcal{T}_n} s(T) = \frac{[z^{n - 1}]}{|T|^k} \prod_{i \geq 1} \mathrm{FOREST}_i(z^i). $$

明显 $\mathrm{forest}_{i, j}$ 是关于 $s(T_{i, 1}), \dots, s(T_{i, |\mathcal{T}_i|})$ 的 $j$ 次对称多项式。它的组合意义是对 $j$ 颗大小为 $i$ 的树数某个东西。

---

这里需要注意

$$[z^{n - 1}]\prod_{i \geq 1} \prod_{T_i \in \mathcal{T}_i} \left(\sum_{j \geq 0} \frac{(s(T_i) z^i)^j}{(j!)^k}\right) $$

并不是关于 $\{s(T) \mid T \in \mathcal{T}\}$ 的对称多项式，所以对于树的大小分开计算是必要的。

---

根据对称多项式基本定理， $\mathrm{forest}_{i, j}$ 可以被

$$s_{i, p} = \sum_{T \in \mathcal{T}_i} \left(s(T_{i})\right)^p $$

表示。最终所求是 $s_{n, 1}$.

之前所做的事情是把 $s_{i, p}$ 表示为 $\mathrm{forest}_{i, j}$，又通过对称多项式基本定理把 $\mathrm{forest}_{i, j}$ 转化为 $s_{i, p}$.

---

用 $s_{i, p}$ 表示 $\mathrm{forest}_{i, j}$

固定 $n$. 现在有

$$\mathrm{FOREST}_n(z) = \sum_{j \geq 0} \mathrm{forest}_{n, j} z^j = \prod_{T \in \mathcal{T}_n} \left(\sum_{j \geq 0} \frac{(s(T) z)^j}{(j!)^k}\right) $$

和

$$s_{n, p} = \sum_{T \in \mathcal{T}_n} s(T)^p.$$

模仿之前证明牛顿恒等式的手法，取对数得

$$\ln \mathrm{FOREST}_n(z) = \sum_{T \in \mathcal{T}_n} \left(\ln \sum_{j \geq 0} \frac{(s(T) z)^j}{(j!)^k}\right). $$

---

这里一个比较投机的方法是考虑

$$G(t) = \ln \sum_{j \geq 0} \frac{t^j}{(j!)^k} = \sum_{j \geq 1} g_j t^j, $$

则

$$\ln \mathrm{FOREST}_n(z) = \sum_{T \in \mathcal{T}_n} G(s(T) z) = \sum_{T \in \mathcal{T}_n} \sum_{j \geq 1} g_j (s(T) z)^j = \sum_{j \geq 1} g_j \left(\sum_{T \in \mathcal{T}_n} s(T)^j \right) z^j = \sum_{j \geq 1} g_j s_{n, j} z^j. $$

即

$$\mathrm{FOREST}_n(z) = \mathrm{exp}\left(\sum_{j \geq 1} g_j s_{n, j} z^j\right). $$

---

计算的目标

以上分析了为了计算 $s_{n, 1}$，需要

$$\{\mathrm{forest}_{i, j} \mid 1 \leq i < n \wedge 1 \leq j \leq \frac{n}{i}\}. $$

因此又需要

$$\{s_{i, p} \mid 1 \leq i \leq n \wedge 1 \leq p \leq \frac{n}{i}\}. $$

为此有

$$s_{n, p} = \sum_{T \in \mathcal{T}_n} s(T)^p = \frac{[z^{n - 1}]}{n^{{\color{red}p}k}} \prod_{i \geq 1} \prod_{T_i \in \mathcal{T}_i} \left(\sum_{j \geq 0} \frac{(s(T_i)^{\color{red}{p}} z^i)^j}{(j!)^{{\color{red}{p}}k}}\right). $$

---

从而需要令

$$\mathrm{FOREST}_{i, {\color{red}p}}(z) = \prod_{T_i \in \mathcal{T}_i}\left(\sum_{j \geq 0} \frac{(s(T_i)^{\color{red} p} z)^j}{(j!)^k}\right) = \sum_{j \geq 0} \mathrm{forest}_{i, j, {\color{red}p}} z^{j}. $$

于是

$$s_{n, p} = \frac{[z^{n - 1}]}{n^{pk}} \prod_{i \geq 1} \mathrm{FOREST}_{i, p}(z^i). $$

---

$$G_p(t) = \ln \sum_{j \geq 0} \frac{t^j}{(j!)^{{\color{red} p}k}} = \sum_{j \geq 1} g_{p, j} t^j $$

所以

$$\exp \ln \mathrm{FOREST}_{i, p}(z) = \exp \left(\sum_{T \in \mathcal{T}_i} G_p(s(T)^p z)\right) = \exp\left(\sum_{j \geq 1} g_{p, j} s_{i, pj} z^j\right). $$

总之

$$s_{n, p} = \frac{[z^{n - 1}]}{n^{pk}} \prod_{i = 1}^{n - 1} \mathrm{exp}\left(\sum_{j = 1}^{\lfloor n / i \rfloor} g_{p, j} s_{i, pj} z^{ij}\right). $$

---

可以证明 $n p \leq N$ 总成立。在第 $i$ 个因子中，有 $i j \leq n$. 所以 $i (pj) \leq N$ 仍然成立。

---

从生成函数翻译成递推

预处理 $G_{p}(z) \bmod \Omega(z^{n / p})$

给出 $f(z)$, 为了计算 $g(z) = \ln f(z)$.

$$\begin{array}{rrcl} & [z^{k - 1}] g'(z) f(z) & = & [z^{k - 1}] f'(z) \\ \implies & \sum_{i = 0}^{k - 1} ((k - i) g_{k - i}) f_i & = & k f_k \\ \implies & k g_k & = & k f_k - \sum_{i = 1}^{k - 1} ((k - i)g_{k - i}) f_i \end{array} $$

具体实现时可以先保留 $k g_k$，最后再除 $k$. 这样最内层循环只需要一次乘法。

这部分的时间复杂度是 $\sum_{p = 1}^n \left(\frac{n}{p}\right)^2 = O(n^2)$.

---

计算 $\exp$

把计算 $\ln$ 的过程倒过来，即可 $O(n^2)$ 计算 $\exp$.

设

$$\gamma_{i, p}(z) = \mathrm{exp}\left(\sum_{j = 1}^{\lfloor n / pi \rfloor} g_{p, j} s_{i, pj} z^{\color{red}j}\right). $$

计算 $\gamma_{i, p}(z)$ 的时间复杂度是

$$\sum_{i p \leq n} \left(\frac{n}{ip}\right)^2 = O(n^2 \log n). $$

---

令

$$\Gamma_{i, p}(z) = \prod_{t = 1}^i \gamma_{t, p}(z) = \Gamma_{i - 1, p}(z) \gamma_{i, p}(z^i). $$

计算 $\Gamma_{i, p}(z)$ 的时间复杂度是

$$\sum_{p = 1}^n \sum_{i = 1}^{\lfloor n / p\rfloor} \frac{n}{p} \frac{n}{ip} = \sum_{p = 1}^n O(\frac{n^2}{p^2} \log \frac{n}{p}) = O(n^2 \log n). $$

总结

• 事实上，这里 $G(t)$ 的系数对应了官方题解中的带权稳定化子。
• 通过对称多项式的理论，回答了（我的）疑问：明明 $|\mathcal{T}_n|$ 的大小是指数增长的，为什么可以多项式级别的信息维护，得到有指数个变量的某个表达式的值。
• 尽量从暴力出发，分析出了为什么各种题解中需要计算诸如「$j$ 颗大小为 $i$ 的树的等价类的 $pk$ 次方的和 」。