题解：速度宾果游戏概率计算的组合分析

---

问题分析

这是一个速度宾果游戏的概率计算问题：

• 有 $n$ 位玩家，每人有 $k$ 个数字（可重复）
• 玩家反应速度排序：玩家 $1$ 最快，玩家 $n$ 最慢
• 当喊出一个数字时，拥有该数字且反应最快的玩家划掉自己的一个副本
• 游戏进行到所有 $n \times k$ 个数字都被喊出
• 问：每位玩家最后完成的概率

---

关键观察

1. 最后完成的等价条件

对于玩家 $i$ 来说，他最后完成当且仅当：

• 对于玩家 $i$ 拥有的每个数字 $x$，在所有喊出 $x$ 的时刻中，分配给玩家 $i$ 的那个喊出是最后出现的

2. 数字的分配规则

考虑一个特定的数字 $x$：

• 设 $cnt_x$ 是 $x$ 在所有玩家卡片中出现的总次数
• 当 $x$ 被喊出时，总是由当前仍拥有 $x$ 的最快玩家划掉
• 因此，$x$ 的 $cnt_x$ 次喊出会按玩家速度顺序分配

3. 简化分析

实际上，我们可以将问题转化为：

• 对于每个数字 $x$，将其 $cnt_x$ 次喊出视为 $cnt_x$ 个"令牌"
• 这些令牌按玩家速度顺序分配给拥有 $x$ 的玩家
• 玩家 $i$ 最后完成 $\Leftrightarrow$ 对于玩家 $i$ 拥有的每个数字 $x$，分配给他的令牌在所有令牌中是最后出现的

---

算法框架

第一步：统计全局出现次数

• 使用映射 app 统计每个数字 $x$ 在所有玩家中出现的总次数 $cnt_x$
• 对每个玩家的数字排序，便于后续比较

第二步：处理玩家优先级

对于每个玩家 $i$（按速度从快到慢处理）：

1. 标记独占数字：

   • 检查玩家 $i$ 的每个数字 $x$
   • 如果对于所有 $j > i$（更慢玩家），玩家 $j$ 不拥有 $x$，则 $x$ 对玩家 $i$ 是"独占"的
   • 因为更慢玩家不会与玩家 $i$ 竞争这些数字

2. 计算贡献：

   • 对于玩家 $i$ 的每个独占数字 $x$，将 $cnt_x$ 加到 num[i] 中
   • 然后将 $cnt_x$ 置为 $0$，防止后续玩家重复计算

第三步：概率计算

玩家 $i$ 最后完成的概率为：

$$P_i = \frac{\text{num}[i]}{n \times k}$$

其中：

• $\text{num}[i]$：玩家 $i$ 独占的数字在所有玩家中的总出现次数
• $n \times k$：所有数字出现的总次数

---

正确性证明

核心引理

玩家 $i$ 最后完成的概率等于他独占的数字占总数字的比例。

证明思路：

1. 考虑随机喊出所有 $n \times k$ 个数字的顺序
2. 对于玩家 $i$ 的独占数字 $x$，由于没有更慢玩家拥有 $x$，分配给玩家 $i$ 的喊出一定是 $x$ 的最后一次喊出
3. 因此，玩家 $i$ 最后完成的时刻由他拥有的某个独占数字的最后一次喊出决定
4. 由于数字喊出顺序完全随机，每个数字的最后一次喊出在序列中的位置是均匀随机的
5. 玩家 $i$ 最后完成 $\Leftrightarrow$ 他某个独占数字的最后一次喊出是整个序列的最后一次喊出
6. 这个概率正是独占数字出现次数占总次数的比例

公式推导

设玩家 $i$ 独占的数字集合为 $E_i$，则：

$$P_i = \frac{\sum_{x \in E_i} cnt_x}{n \times k}$$

其中 $cnt_x$ 是数字 $x$ 在所有玩家中的出现次数。

---

复杂度分析

• 时间复杂度：$O(n^2 \cdot m \log m)$
  • 对每个玩家的数字排序：$O(n \cdot m \log m)$
  • 对于每对玩家 $(i, j)$（$i < j$），比较数字集合：$O(m)$（使用双指针）
  • 总比较次数：$O(n^2 \cdot m)$

对于 $n \le 100, m \le 1000$，最坏约 $10^7$ 次操作，可接受。

• 空间复杂度：$O(n \cdot m)$ 存储所有数字

---

算法步骤

1. 输入处理：

   • 读取 $n, m$
   • 读取每个玩家的 $m$ 个数字
   • 统计每个数字的全局出现次数 app

2. 排序预处理：

   • 对每个玩家的数字数组排序

3. 计算独占数字：

   • 对于每个玩家 $i$（从快到慢）：
     • 初始化标记数组 hvs
     • 对于每个更慢玩家 $j > i$，标记玩家 $i$ 与 $j$ 的公共数字
     • 对于玩家 $i$ 的每个数字，如果是独占的（未被标记），则将全局计数加到 num[i]，并清零全局计数

4. 输出概率：

   • 对于每个玩家 $i$，输出 num[i] / (n * m)

---

总结

本题是一道组合概率与集合分析的题目，主要考察：

1. 问题转化能力：将复杂的游戏过程转化为数字的全局统计
2. 独占性分析：识别玩家最后完成的关键在于独占数字
3. 概率计算：将概率转化为比例计算

算法的核心洞察在于：

• 玩家最后完成的事件等价于他某个独占数字的最后一次出现是全局最后一次出现
• 独占数字的判定基于玩家速度优先级
• 概率计算简化为简单的比例问题

这种"独占性+比例计算"的方法巧妙避免了复杂的条件概率计算，展示了如何通过深入分析问题本质来简化计算。