QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: jiangly

Posted at: 2025-12-13 00:01:47

Last updated: 2025-12-13 00:01:50

Back to Problem

题解

答案等于 $N$ 加上选择的其他评论的个数的期望。由期望的线性性只需要考虑每条其他评论在自己的所有评论之后出现的概率。

问题可以看作不断随机选择评论 (可能是已经被删除的) 并将其删除,则答案就是 $\frac{B}{\sum_{i=1}^NA_i+B}$ 乘上恰好自己的所有评论被删除这个状态持续时间的期望。这也就是对所有 $S\sub [N]$ 求出只有 $S$ 以外的自己的评论被删除的状态的持续时间的期望乘上 $(-1)^{|S|}$ 并求和,前者也就是 $\frac{\sum_{i=1}^NA_i+B}{\sum_{i\in S}A_i+B}$。这只与 $\sum_{i\in S}A_i$ 的分布有关,可以在 $O(N\sum_{i=1}^NA_i)$ 的时间内 DP 预处理后在 $O(\sum_{i=1}^NA_i\log \mathrm{Mod})$ 对每个 $B$ 进行计算。

Comments

No comments yet.