按照常规做法先将值域分为 $O(n)$ 段。
考虑一个人 $i$ 在第 $j$ 段时，其他的人选择的所有情况的概率，注意到其他的人可以分为三类：1. 选段在 $j$ 前。 2. 选了第 $j$ 段。 3. 选段在 $j$ 后。第一类对排名的贡献固定，第二类可以算概率（每个人等价），第三类不对排名造成影响。
那么只需要记录前两类人的数量，直接 dp 的复杂度为 $O(n^5)$ 。
代码：Submission #127571952 – Codeforces
考虑优化，注意到转移过程大部分只和 $b$（当前值域段编号）有关，事实上，对于 $i$ 的更新就是将除了 $i$ 以外的人全部卷起来，接下来就是套路分治了。
dp 转移的时候卡卡上界就能过，时间复杂度 $O(n^4\log n)$ 。
0 条评论