すべての人が持っているカードの数値の XOR を取るとペアとなっているカードは打ち消し合うので奇数枚あるカードの数値が最後に残る.

ここで \(X_N = 0 \oplus 1 \oplus \cdots \oplus N\) を考える. これは \(N \bmod 4\) の値が \(0\) なら \(N\), \(1\) なら \(1\), \(2\) なら \(N+1\), \(3\) なら \(0\) となる. これを使うと, \(x \oplus x+1 \oplus \cdots \oplus y = X_y \oplus X_{x-1}\) となる.

さらに \(S_i = \{ L_i, L_i+2^{D_i}, L_i+2 \cdot 2^{D_i}, \dots, L_i+(K_i-1)2^{D_i} \}\) の XOR を考える.

下位 \(D_i\) ビットはすべて同じ数なので, \(K_i\) が偶数なら \(0\) になり, 奇数なら \(L_i\) の下位 \(D_i\) ビットがそのまま残る.

下位 \(D_i\) ビットを除いた部分については, \(S_i\) の各値を \(D_i\) ビット右シフトした数列 \(T_i\) として \(L_i\) を \(D_i\) ビットだけ右シフトした値を \(M_i\) とすると, \(T_i\) は \(\{ M_i, M_i+1, M_i+2, \dots M_i+(K_i-1) \}\) となる. この XOR は上記を使えば計算できる.

\(T_i\) の XOR を \(D_i\) ビットだけ左シフトして, 下位 \(D_i\) ビットの XOR と合わせれば \(S_i\) の XOR が求まる.

これをすべての \(i\) について計算して XOR を取れば, 余るカードの数値が分かる.