AT_arc208_a [ARC208A] Bitwise OR Game
题目描述
有 $N$ 堆石子,第 $i(1\le i\le N)$ 堆有 $A_i$ 颗石子。
Alice 和 Bob 将用这些石子玩如下的游戏:
- 从 Alice 开始,两名玩家轮流进行操作。
- 每当一个玩家进行操作时,他需要选择一个非空石堆,并从其中移出一个或更多石子。操作的玩家操作时不能改变所有石堆石子个数的按位 $\text{OR}$。
首先不能操作的玩家输。
两名玩家都使用最佳策略,求哪名玩家获胜。
有 $T$ 组数据,你需要分别求解。
::::info[什么是按位 $\text{OR}$?]
非负整数 $A,B$ 的按位 $\text{OR}$,$A\operatorname{OR}B$,定义如下:
- 将 $A\operatorname{OR}B$ 以二进制形式写出,$2^k(k\ge 0)$ 处的二进制位上为 $1$ 当且仅当 $A,B$ 的二进制形式的 $2^k$ 处中至少一个为 $1$,否则为 $0$。
例如,$3\operatorname{OR}5=7$(二进制下为 $011\operatorname{OR}101=111$)。\
一般地,$k$ 个非负整数 $p_1,p_2,p_3,\cdots,p_k$ 的按位 $\text{OR}$ 定义为 $(\cdots((p_1\operatorname{OR}p_2)\operatorname{OR}p_3)\operatorname{OR}\cdots\operatorname{OR}\cdots p_k)$,可以证明它的值和 $p_1,p_2,p_3,\cdots,p_k$ 的顺序无关。
::::
输入格式
第一行一个整数 $T$,表示数据组数。
对于每组数据,第一行一个整数 $N$。
第二行 $N$ 个整数 $A_1,A_2,\cdots,A_N$。
输出格式
对于每组数据,如果 Alice 获胜则输出一行 `Alice`,如果 Bob 获胜则输出一行 `Bob`。
说明/提示
**数据范围**
- $1\le T\le 10^5$
- $2\le N\le 2\times 10^5$
- $N$ 的和最大为 $2\times 10^5$。
- $1\le A_i\le 10^9$
- 所有输入值均为整数。
**样例解释**
对于第一组数据:
初始时,所有石堆石子个数的按位 $\text{OR}$ 为 $3\operatorname{OR}4\operatorname{OR}6=7$。
Alice 可以执行的操作如下:
- 从第一堆中移出两颗石子。
- 从第二堆中移出一颗或更多石子。
- 从第三堆中移出一颗或更多石子。
如果 Alice 从第一堆中移出一颗石子,所有石堆石子个数的按位 $\text{OR}$ 将变为 $2\operatorname{OR}4\operatorname{OR}6=6$。因此,Alice 不能执行此操作。
如果 Alice 从第三堆中取出六颗石子,Bob 在下一步中将无法执行任何操作。因此,两名玩家都执行最优策略时的赢家是 Alice。
由 @[chenxi2009](/user/1020063) 翻译。