\(\oplus\) で XOR 演算を表します。

\(i\) 番目の山の石の個数を \(A_i\) と表記します。また、 \(S=A_1 \oplus A_2 \oplus \ldots \oplus A_N\) とします。

ビット単位 OR 演算による制約が存在しない場合のゲームは Nim という名称で知られており、勝敗は以下のように判定することができます。

• \(S = 0\) なら後手必勝、そうでないなら先手必勝。

この事実は以下のように数学的帰納法で示すことができます。

• \(S= 0\) のとき：
  • XOR の性質より、どのように石を取っても再び \(S= 0\) にすることはできない。
• \(S \neq 0\) のとき：
  • \(S\) の最上位ビットが立っているような \(A_k\) を一つ選ぶ。条件を満たす \(A_k\) は奇数個存在することからこのような選び方が必ず存在することが分かる。
  • \(k\) 番目の山から石を \(A_k - (A_k \oplus S)\) 個取り除く。\(S\) の最上位ビットが \(A_k\) で \(1\) から \(0\) に減り、それより上のビットに変化はないので \(A_k \oplus S < A_k\) が分かるのでこの選択は合法である。

これらを踏まえ、この問題を解くことを考えます。

\(T = A_1\ \mathrm{OR}\ A_2\ \mathrm{OR}\ \ldots \ \mathrm{OR}\ A_N \) とします。

実は、この問題にも類似した必勝法が存在し、以下のように判定することができます。

• \(S = \color{red}T\) なら後手必勝、そうでないなら先手必勝。

この事実は以下のように数学的帰納法で示すことができます。

• \(S= T\) のとき：
  • XOR の性質より、どのように石を取っても再び \(S= T\) にすることはできない。
• \(S \neq T\) のとき：
  • \(S \oplus T\) の最上位ビットが立っているような \(A_k\) を一つ選ぶ。条件を満たす \(A_k\) は \(2\) 個以上存在することからこのような選び方が必ず存在することが分かる。
  • \(k\) 番目の山から石を \(A_k - (A_k \oplus S \oplus T)\) 個取り除く。\(S \oplus T\) の最上位ビットが \(A_k\) で \(1\) から \(0\) に減り、それより上のビットに変化はないので \(A_k \oplus S \oplus T < A_k\) が分かる。さらに、\(S \oplus T\) で立っているビットは \(A\) でも \(2\) つ以上立っているので \(T\) の値も不変である。したがって、この操作は合法である。

この議論により \(S=T\) なら Bob を、そうでないなら Alice を出力すれば良いことが分かります。

以上を適切に実装することでこの問題に正答することができます。計算量はテストケースあたり \(O(N)\) です。

実装例(Python3)

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    s, t = 0, 0
    for v in a:
        s ^= v
        t |= v
    if s == t:
        print("Bob")
    else:
        print("Alice")