题解：CF2125D Segments Covering
Karieciation
·
·
题解
题目大意
给出一些线段，存在地概率是 \dfrac{p}{q}，要求求出每个点被覆盖且只被一条线段覆盖地概率。
解题思路
乍一看感觉不好写，但是不妨我们可以构造一下：设初始时没有线段覆盖，我们不妨从前往后覆盖，很容易想到可以给 n 条线段排一下序，然后我们考虑一下 dp：设 f_i 为当前线段选了的话的成功的总概率，o_i 为以 i 结尾的大线段已经符合了题意，且对于 \forall i+1\le j\le n，j 位置没有线段覆盖的总概率。
$$o_i=\prod_{i=1}^{n}{\dfrac{q-p}{q}}$$
由于每一条新放的线段都假设它从来没有放入，所以状态转移方程应该从 $o_{l_i-1}$ 转移过来，并且除掉不放当前线段的概率，乘上放入当前线段的概率，即 $\div\dfrac{q-p}{q}\times\dfrac{p}{q}$（即 $\times\dfrac{p}{q}\times\dfrac{q}{q-p}$）。
由此得出：
$$f_i=o_{l_i-1}\times\dfrac{p}{q}\times\dfrac{q}{q-p}$$
$o_i$ 的转移显而易见：
$$o_i=o_i+\sum_{i=1}^{n}{f_i}(r_i=i)$$
显然，每当我们统计出来一个 $f_i$，我们随之更新相应的 $o_i$ 就好了。
简单证明一下不难发现这个操作是没有后效性的，符合 $dp$ 条件，题目答案即为 $o_m$。
### [AC代码](https://codeforces.com/contest/2125/submission/330438599)