题解：P17856 [LBA-OI R6 D] 奶龙游戏

· · 题解

奶龙不都是 2 吨的吗。

先给奶龙从大到小排序，当第 i 个奶龙分给 Alice 时记作 +1，给 Bob 记作 -1。

记前缀和为 s_i，则当且仅当 Alice 必须恰好赢 k 轮时必须满足 n-k \le s_i \le k。

:::success[证明] 记前 i 只奶龙中 Alice 有 a_i 只，b_i 同理，那么 a_i-b_i=s_i。

把上面那个式子带进 s_i\le k 可以得到 a_i-b_i\le k，也就是如果前 i 只奶龙中 Alice 的数量比 Bob 多了 k+1 个及以上，那么 Alice 就不可能只赢 k 局。

另外一个式子也是同理，即 b_i-a_i\le n-k，也就是 Alice 最多只能输 n-k 把，但是如果在前 i 只奶龙中的 Bob 的数量比 Alice 的数量多 n-k+1 个及以上，那么 Alice 就无法赢 k 局。

那么总方案数为 \binom{2n}{n}。

$s_i<n-k$ 的方案数为 $\binom{2n}{k-1}$。 最后的方案数就是 $\binom{2n}{n}-\binom{2n}{n-k-1}-\binom{2n}{k-1}$，然后除上总的方案数 $\binom{2n}{n}$ 就能得到概率了。