CF1153F Serval and Bonus Problem

发表于 分类于 ， ， 阅读次数：

题意：一条长为 的线段，随机覆盖 个区间（端点均匀随机），问被覆盖 次（及以上）的区域的期望长度。

答案对 取模，，时限 。

显然，这个问题具有线性性，不妨改设线段长为 ，最后将答案乘 。

设函数 为：线段上位置为 的地方被覆盖 次（及以上）的概率。答案为 该积分难以直接求解。不过，它有一个组合意义：随机选一个点被覆盖 次的概率。

考虑 个区间的 个端点，加上一个随机采样点，共 个独立随机的“关键点”。我们只对采样点被覆盖的次数感兴趣，故只对关键点的相对排列位置感兴趣。

显然所有排列的出现概率是相同的。因此，我们只需要考虑离散的排列，复杂的几何概型成功转化为熟悉的古典概型。

考虑 DP。

设 为：从左往右填写排列，已经填了 个左端点， 个右端点，随机采样点是否放置（如果已经放置，要求放置处必然被多于 条线段覆盖）的方案数。

注意，我们认为左端点之间没有顺序之分，右端点追随与之配对的左端点。

边界：。

转移：

  • 选择左端点：

  • 选择右端点（并选择一个已有的左端点配对）：

  • 选择随机采样点：

复杂度 。

除以总方案数就得到概率。总方案数可以把限制 去掉之后，用同样的 DP 计算。