按照常规做法先将值域分为 $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)$ 。

代码:Submission #127572775 – Codeforces

分类: 文章

Qiuly

QAQ

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code