自动搬运

查看原文

来自洛谷，原作者为

	一只书虫仔 End.

搬运于2025-08-24 22:24:42，当前版本为作者最后更新于2021-05-09 19:25:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

Description

随机生成一棵 $n$ 个点的树，运行机制为对于点 $i$，在 $[1,i-1]$ 中随机挑选一个点 $j \in [1,i-1]$ 作为 $i$ 的父亲节点，概率均等，求所有可能生成的树中节点 $k$ 的度数之和。

Solution

对于点 $p$ 而言，他的度数分为两部分，一部分是父亲节点，贡献为 $1$，但是要注意节点 $1$ 没有父亲节点，要省掉；一部分是儿子节点，对于每个点 $p' \in [p+1,n]$，都有可能在 $[1,p'-1]$ 中随机挑选一个点作为他的父亲，而选中是点 $p$ 的概率即为 $\frac 1 {p'-1}$。而节点为 $n$ 的树一共有 $\displaystyle \prod\limits_{i=1}^{n-1}i$ 种，故答案应为：

$$\displaystyle \prod\limits_{i=1}^{n-1}i \times \sum\limits_{p'=p+1}^n \frac 1 {p'-1}+[p\ne 1] \times \displaystyle \prod\limits_{i=1}^{n-1}i $$

具体实现细节用逆元就可以了，预处理逆元和阶乘然后求一下前缀和即可。