[ZJOI 2018] 树

· · 题解

ZJOI 2018 - 树

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

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

解法

转化为递归构造

设 \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}.
例子
$$ e_3 = x_1x_2x_3 + x_1x_2x_4 + x_1x_3x_4 + x_2x_3x_4. $$ --- [牛顿恒等式](https://en.wikipedia.org/wiki/Newton%27s_identities) 指出 $$ 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)$. ##### 对称多项式基本定理 [对称多项式基本定理](https://en.wikipedia.org/wiki/Elementary_symmetric_polynomial#Fundamental_theorem_of_symmetric_polynomials)指出，任意 $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).

总结