P6862 题解

· · 题解

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

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