ゲームの状態が与えられた時，その grundy 数は以下のように求まります．

x=0
for 1 <= i <= N:
    x ^= A[i]
for 1<= i < j <= N:
    x ^= (A[j]-A[i])^(A[j]-A[i]-1)
return x

二重ループの部分は，「各 \(0 \leq k\) に対し，下位 \(k\) bit が等しい数のペアの個数が奇数なら \(2^k\) の寄与がある」と考えると見通しが良いです．

上記のコードの出力を \(f(A)\) と書くことにします． \(f(A)\) が grundy 数に等しいことを以下で証明します．

\(\max(A_i) < 2^L\)として，\(L\) に関する帰納法で証明します．

\(L=1\) の場合は明らかです． 今，\(L \geq 2\) であり，\(L=l-1\) について命題が正しいとします．

まず，操作を行うことで \(f(A)\) の値が必ず変化することは簡単に確認できます． 次に，\(f(A)\) の値を \(x \rightarrow y\) (\(x>y\)) と変化させたいとします． \(z=x \oplus y\) とおくと，\(z\) の最上位 bit の桁は \(x\)において \(1\) になっています．

まず，\(z\) が偶数である場合を考えます． この場合に行う手は，奇数を奇数に変化させるか，偶数を偶数に変化させるかのどちらかです． \(A\) の中の奇数を \(2\) で割った商の集合を \(odd\)，偶数を \(2\) で割った商の集合を \(even\) とすると，\(f(odd),f(even)\) のいずれかは，\((z/2)\) の最上位 bit の位置で \(1\) になっています．つまり \(L=l-1\) の場合に帰着できます．

\(z\) が奇数である場合を考えます． \(z=2w+1\) であるとします．

各 \(0 \leq k < 4\) について \(A\) の要素で \(\bmod 4\) で \(k\) になる値を \(B_{k,1}<B_{k,2}<\cdots<B_{k,S_k}\) とします． \(A\) から \(v\) を選んで \(v \rightarrow v'\) と操作することにすると，\(v'\bmod 4\) の値は \(v \bmod 4\) から一意に定まります． \(\bmod 4\) で考えたときに \(0,1,2,3\) それぞれについて変化先が定まりますが，これは互いに行き来する関係になることが確認できます．（つまり \(p \rightarrow q\) と変化させるべきなら \(q \rightarrow p\) でもある．）

今，\(0\) と \(1\)，\(2\) と \(3\) が互いに行き来しているとします． \(\bmod 4\) で \(0,1\) の中から値を選んで操作することを考えます． \(c_{0,i}=B_{0,i}/4 \times 2,c_{1,i}=B_{1,i}/4\times 2+1\) と定義します．ここで割り算はすべて切り捨てとします． このとき，\(\{c_{0,i},c_{1,i}\}\) に対して，\(f(\{c_{0,i},c_{1,i}\})\) を \( \oplus (w|1)\) で変化させる手があれば，それに対応する手を \(A\) に対して行うことができ，補題が示されます． 同様に \(c_{2,i},c_{3,i}\) を定義し，こちらを使った操作も考えることができます．

ここで，\(w \geq 2\) の場合は，\((w|1)\) の最上位 bit は \(w\) と同じです．これが \(2^p\) (\(p \geq 1\)) の桁だとします．ところで，\(2^{p+1}\) は \(z\) の最上位 bit の桁なので，\(f(A)\) の \(2^{p+1}\) の桁は \(1\) です．すると \(c_{k,i}\) の定義より，\(f(\{c_{0,i},c_{1,i}\})\) もしくは \(f(\{c_{2,i},c_{3,i}\})\) の\(2^p\) の桁が \(1\) であることになるので，\(L=l-1\) のケースに帰着できることになります．

\(w=0,1\) のケースでも，\(f(\{c_{0,i},c_{1,i}\})\) もしくは \(f(\{c_{2,i},c_{3,i}\})\) が奇数になることが確認できるため，\(L=l-1\) のケースに帰着できます． 各 \(k\) の個数分布 \(S_k\) の \(\bmod4\) だけが重要であることがわかるので，これらをすべて全探索し，\(x>x\oplus z\) であるような組で主張が成立することを確かめることができます．

\(0\) と \(3\)，\(2\) と \(1\) が互いに行き来している場合も同様に全探索で示すことができます．

よって示されました．