标签：sum 做题 ans 区间 概期 DP

概期DP

P3600

考虑 \(ans \in [1, x]\)，那么有:

\[\begin{aligned} E(ans) &= \sum_{i \in [1,x]} iP(ans = i) \\ &= \sum_{i \in [1,x]} P(ans \geq i) \\ &= \sum 1 - P(ans < i) \\ &= x - \sum P(ans < i) \end{aligned} \]

我们就只需要计算 \(P(ans < a)\)，这个东西我们分析一下发现就相当于每个区间都要出现 $ < a$ 的数。我们考虑DP。
思考最后的序列的特征就是若干个 \(< a\) 的数，这些数要覆盖所有的区间，那么我们状态就设这个，其他的数没有任何限制。
\(f_i\) 表示放了前 \(i\) 个数，第 \(i\) 个数是 \(< a\) 的。转移很简单，我们枚举上一个位置为 \(j\) 的 $ < a$ 的数，中间的只能 \(\geq a\)，不然会算重。

还有一个限制就是前 \(i\) 个一定覆盖了前缀所有的区间，我们把包含的区间丢掉，然后按 \(l\) 排序，那么每个点会覆盖到区间就是一段连续的区间 \(l_i,r_i\)，那么最终的转移就是，设 \(p = \frac{a}{x}\):

\[f_i = \sum_j [l_i \leq r_j] f_j * (1 - p)^{i - j - 1} \]

明显可以双指针加前缀和优化做到 \(O(n)\)。

最后 \(p(ans < a) = \sum_{i} [r_i = m] f_i * (1 - p)^{n - i}\)

对于每一个 \(a\) DP一遍即可，时间复杂度 \(O(n^2)\)。

标签：sum,做题,ans,区间,概期,DP
From： https://www.cnblogs.com/qerrj/p/18397250