この解説では Grundy 数の知識を前提とします。

以下のゲームを考えます。

\(x\) 個の石の山がある。Alice から始めて交互に \(1\) 個以上 \(K\) 個以下の石を取る。先に石を取れなくなった方の負けである。

このゲームの Grundy 数は \(g(x)=x\bmod (K+1)\) であることが知られています。証明も帰納的に簡単に示すことができます。

\(i+j\) が奇数であるような \((i,j)\) それぞれに対する \(g(A_{i,j})\) の多重集合を \(S\) とします。

実は、このゲームで Bob が勝つことは \(\displaystyle \bigoplus_{x \in S} x = 0\) と同値です。このことを示します。

[1] \(\displaystyle \bigoplus_{x \in S} x = 0\) のとき

どのように操作しても \(\displaystyle \bigoplus_{x \in S} x\neq 0\) となることを言えば良いです。

\(i+j\) が偶数であるような \((i,j)\) を選び操作した場合、\(S\) の \(1\) つの値が変化します。XOR の性質より、元々総 XOR が \(0\) であったため \(\displaystyle \bigoplus_{x \in S} x = 0\) になることはありません。

\(i+j\) が奇数であるような \((i,j)\) を選び操作した場合も \(S\) の \(1\) つの値が変化するので同じことが言えます。

[2] \(\displaystyle \bigoplus_{x \in S} x \neq 0\) のとき

通常の Nim と同じ議論により、\(\displaystyle \bigoplus_{x \in S} x = 0\) となる操作が必ず存在します。

以上より、\(i+j\) が奇数であるような \(g(A_{i,j})\) の総 XOR が \(0\) ならば Bob を、\(0\) でないならば Alice を出力すれば良いです。

以上を適切に実装することでこの問題に正答することができます。

実装例(Python3)

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n, k = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    res = 0
    for i in range(n):
        for j in range(n):
            if (i + j) % 2 == 1:
                res ^= a[i][j] % (k + 1)
    print("Alice" if res != 0 else "Bob")

原案：kyopro_friends