AT_arc148_d [ARC148D] mod M Game
题目描述
黑板上写有 $2N$ 个整数 $A_1,\ A_2,\ \dots,\ A_{2N}$。另外,给定一个不小于 $2$ 的整数 $M$。
Alice 和 Bob 进行一个游戏。游戏由 Alice 先手,双方轮流进行如下操作,直到黑板上的数全部被消除:
- 选择一个数,将其从黑板上消去。
当游戏结束时,如果(Alice 消去的数的和)$\bmod\ M$ 与(Bob 消去的数的和)$\bmod\ M$ 相等,则 Bob 获胜,否则 Alice 获胜。
假设双方都采取最优策略,问最终谁会获胜?
输入格式
输入以如下格式从标准输入读入:
> $N$ $M$ $A_1$ $A_2$ $\dots$ $A_{2N}$
输出格式
如果 Alice 获胜,输出 `Alice`;如果 Bob 获胜,输出 `Bob`。
说明/提示
## 限制条件
- $1 \leq N \leq 2 \times 10^5$
- $2 \leq M \leq 10^9$
- $0 \leq A_i \leq M - 1$
- 所有输入均为整数
## 样例解释 1
游戏的一个进行过程如下:
- Alice 消去 $1$。
- Bob 消去 $4$。
- Alice 消去 $5$。
- Bob 消去 $8$。
如此进行后,Alice 消去的数的和 $\bmod\ 9$ 为 $(1 + 5) \bmod 9 = 6$,Bob 消去的数的和 $\bmod\ 9$ 为 $(4 + 8) \bmod 9 = 3$,$6 \neq 3$,因此 Alice 获胜。
由 ChatGPT 4.1 翻译