题解：P15111 群星

harmis_yz · 2026-11-09 10:48:07 · 题解

我觉得难点在 DP 啊。为啥题解叽里咕噜说一坨期望怎么算。

分析

设当前排名为 x，观察发生一场战争后排名的期望。

分情况讨论：

期望为：

当 n \ge 3 时上面这个期望值随 x 增加单调不减。先不考虑 n < 3 的情况。

记 g(x,y) = (1-\frac{2}{n-1})\cdot g(x,y-1) + (1+\frac{2}{n-1})。

那么策略应该是在选择的时候直接选能选的中排名最小的那个。如果在世纪 i 能选择的最小排名为 x，那么答案就是 g(x,\sum\limits_{j\ge i}^{}a_j)。

记 f(x,c) 表示排名为 1\sim i 的文明中被选择的文明数量为 c 的概率。那么能选择的最小排名为 x 的概率就是 f(x-1,x-1)-f(x,x)。

定义状态函数 f_{i}(x,c) 为考虑到当前时刻，排名为 1\sim x 的文明中被选择的文明数量为 c 的概率。

世纪初，有：f_{i}(x,\min(c+1,x))=f_{i-1}(x,c)。

对于 f_i(x,c)，可知排名 [1,x] 中有 c 个，[x+1,n] 中有 i-c 个。观察发生一场战争后的局面，分类讨论：

1. 交换的文明对都不是被选择的文明。新状态为 (x,c)。概率 \frac{\binom{n-i}{2}}{\binom{n}{2}}。
2. 交换的文明对恰有一个是被选择的文明。
   1. 被选择的文明在 [1,x]，没被选择的文明在 [1,x]。新状态为 (x,c)。概率 \frac{c\cdot (x-c)}{ \binom{n}{2}}。
   2. 被选择的文明在 [1,x]，没被选择的文明在 [x+1,n]。新状态 (x,c-1)。概率 \frac{c\cdot (n-x-(i-c))}{\binom{n}{2}}。
   3. 被选择的文明在 [x+1,n]，没被选择的文明在 [1,x]。新状态 (x,c+1)。概率 \frac{(x-c)\cdot (i-c)}{\binom{n}{2}}。
   4. 被选择的文明在 [x+1,n]，没被选择的文明在 [x+1,n]。新状态 (x,c)。概率 \frac{(i-c)\cdot (n-x-(i-c))}{\binom{n}{2}}。
3. 交换的文明对都是被选择的文明。
   1. 都在 [1,x]。新状态 (x,c)。概率 \frac{\binom{c}{2}}{\binom{n}{2}}。
   2. 都在 [x+1,n]。新状态 (x,c)。概率 \frac{\binom{i-c}{2}}{\binom{n}{2}}。
   3. 一个在 [1,x]，一个在 [x+1,n]。新状态 (x,c)。概率 \frac{c\cdot (i-c)}{\binom{n}{2}}。

整理一下，记转移前状态函数为 f'_i(x,c)，转移后为 f_{i}(x,c)。有：

发生 a_i 场战争就是转移 a_i 次。矩阵快速幂优化做到转移 O(n^4\log a_i)。

整体复杂度 O(kn^4\log \max(a_i)+kn\log(\sum a_i))。

不是，数据里怎么没有 n< 3 的情况啊。