期望与概率2
徐晨轩✅
·
·
个人记录
E
可以对每个人单独考虑，再求和。
注意到 \sum P(=i) \times i = \sum P(\ge i)，那么我们只需要求出身高为 i 的人的视野期望。这是简单的。
F
考虑 DP。prob_i 表示第 i 张卡被使用的概率（一张卡最多被使用一次），那么 \sum prob_i \times d_i 即为答案。
令 f_{i, j} 表示前 i 张卡用了 j 张的概率。递推式是显然的。
G
考虑令 f_i 表示 i 走向父亲（根即为终点）的期望步数。易得 f_i 的表达式。那么终点为根的答案即为 \sum f_i \times sz_i。对于所有根，进行换根 DP 即可。注意最后答案要除以 n^2。