2以上離れた要素は独立に扱える. ということで差が1のかたまりごとに行う Nim となる. よって, 差が1のかたまりの個数をキーにした grundy 数を計算してその XOR をとればいい.

この grundy 数を \(g(n)\) とする. \(n \geq 3\) については,

\[g(n) = {\rm mex}(g(n-2), g(0) \oplus g(n-3), g(1) \oplus g(n-4), g(2) \oplus g(n-5),\dots)\]

となる. これを愚直に計算すると \(O(N^2)\) なので間に合わない.

しかし, 計算してみると \(n\) が小さいときを除けば周期34で繰り返している. そのため大きいgrundy数は計算しなくてもいい.