2022.08.06

CF1153F Serval and Bonus Problem

洛谷：CF1153F

Codeforces：CF1153F

Solution 1

首先指明，随机出来的两个点重合的概率很小，我们忽略不计。

那么我们会随机出来 \(2n\) 个不重合的点，又由于不与端点重合，因此会随机出 \(2n+1\) 个长度未知的区间。

由于点的位置随机，这 \(2n+1\) 个区间的期望长度应该相等，均为 \(\frac{l}{2n+1}\)。

总期望长度 = 各期望长度 * 被覆盖 \(k\) 次以上的概率 之和。

于是我们只需要知道每个区间被覆盖 \(k,k+1,\cdots,n\) 次的概率。

我们可以求出把一个区间覆盖 \(w\) 次的方案数，然后用这个方案数除以总方案数。

总方案数即为把 \(2n+1\) 个区间全部覆盖完的方案数。

具体求每个区间覆盖 \(w\) 次的方案数时，要用 dp 转移。

这个 dp 很 鬼畜 有意思：

设 \(f_{i,j}\) 为选定了前 \(i\) 个点，其中第 \(i\) 个点之后的第一个区间被覆盖了 \(j\) 次的方案数。

边界为 \(f_{0,0}\)，即第一个点之前的区间一定不会被覆盖。

转移：

若第 \(i+1\) 个点是起始点，那么第 \(i+1\) 个点后的那个区间多一层覆盖，即 \(f_{i+1,j+1}+=f_{i,j}\)。

若第 \(i+1\) 个点是结束点，那么第 \(i+1\) 个点后的那个区间少一层覆盖，又因为这个结束点可以结束 \(j\) 个覆盖中的任意一条，因此有 \(f_{i+1,j-1}+=j\times f_{i,j}\)。

统计答案时，枚举每一个区间，枚举覆盖数 \(j:k\to n\)，\(ans+=f_{i,j}\times f_{2n-i,j}\times j!\)。

前后到 \(i\) 把那里的区间覆盖 \(j\) 次的方案数乘起来然后乘上安排这 \(j\) 个覆盖的排列数。

最后要除以总方案数 \(f_{2n,0}\)，再乘上期望长度 \(\frac{l}{2n+1}\)。

code CF1153F