\(A=(A_1,A_2,\dots,A_N)\) に含まれる相異なる数が昇順に \(B_1,B_2,\dots,B_M\) であり，\(B_i\) は \(A\) に \(C_i\) 個含まれるとします．また，\(X := (B_1,C_1,B_2-B_1,C_2,\dots,B_M-B_{M-1},C_M)\) とします．\(X\) は長さ \(2M\) の列です．

このとき，問題のゲームは以下のゲームと同じであることがわかります:

石の山が \(2M\) 個あり，山 \(i\) には石が \(X_i\) 個ある．Alice と Bob は交互に，石が \(1\) 個以上残っている山のうち最も番号が小さいものから，\(1\) つ以上の石を取る．行動できなくなった方が負けである．

\(\mathrm{dp}[i]\) を，山 \(1,2,\dots,i\) の石がすべてなくなり，それ以降の山は元のままである状態で先手が勝つことができるなら true，そうでないなら false とすると，\(\mathrm{dp}[i]\) を \(i\) の降順にそれぞれ \(O(1)\) 時間で求めることができます．