「CF1096E」The Top Scorer

发表于 更新于 分类于 本文字数： 756 阅读时长 ≈ 1 分钟

Description

Link：CF1096E

有 pp 个人玩一个游戏，第 ii 个人的得分为 aia_i。

已知 ∑ai=s\sum a_i = s 且 a1≥ra_1 \geq r，得分最高的人可以获胜，若多个人得分最高，则等概率随机其中一个人获胜。

求第一个人获胜的概率，答案对 998244353998244353 取模。

数据范围：1≤p≤1001 \leq p \leq 100，0≤r≤s≤50000 \leq r \leq s \leq 5000。

时空限制：33s / 250250MiB。

Solution

naive：枚举最大值 mx\mathrm{mx}，枚举最大值个数 cc，计算剩余选手得分 <mx< \mathrm{mx} 且和等于 s−mx⋅cs - \mathrm{mx} \cdot c 的方案数。

不妨去掉小明得分 ≥r\geq r 的限制，此时每个人成为冠军的概率均等，均为 1n\frac{1}{n}。

“小明得分 ≥r\geq r 且小明是冠军” 等价于 “冠军得分 ≥r\geq r 且小明是冠军”，故我们只需计算冠军得分 ≥r\geq r 的概率，最后乘以 1n\frac{1}{n} 即可。

考虑容斥，钦定 ii 个选手得分 ≥r\geq r，先将这 ii 个选手的得分减去 rr，故我们需要计算选手得分总和为 s−i⋅rs - i \cdot r 的方案数，运用插板法可得

∑i=1n(−1)i+1(ni)(s−i⋅r+n−1n−1)\sum\limits_{i = 1}^n (-1)^{i + 1} \binom{n}{i} \binom{s - i \cdot r + n - 1}{n - 1}