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 翻译