本問題を解くには前提として Grundy 数の知識が必要です。 ここではそれを既知として解説します。 Grundy 数について本解説の後ろで簡単にですが説明しています。より詳しいことは、インターネット検索等をご活用ください。

非負整数 \(n\) に対して、ちょうど \(n\) 個の石からなる山 \(1\) 個のみからなる局面の Grundy 数を \(g(n)\) で表します。 本問題を解くには、\(g(A_1), g(A_2), \ldots, g(A_N)\) が求まれば良いです。 よって、適切な前計算によって、所望の非負整数 \(n\) に対して \(g(n)\) を高速に求めることができる状態を作ることを目指します。

非負整数 \(n\) に対して、 \(h(n) := \max \lbrace g(0), g(1), \ldots, g(n) \rbrace\) と定義します。 また、\(\mathcal{S} := \lbrace 0, X_1, X_2, \ldots, X_M \rbrace\) とします。 このとき、\(g(0), g(1), \ldots, g(n-1)\) の中に \(0, 1, 2, \ldots, h(n-1)-1, h(n-1)\) はそれぞれ一回以上は出現するため、 もし \(n \not\in \mathcal{S}\) であれば

\[g(n) = \mathrm{mex}\lbrace g(0), g(1), \ldots, g(n-1) \rbrace = h(n-1) + 1,\]

\[h(n) = \max\lbrace h(n-1), g(n) \rbrace = h(n-1) + 1\]

が成り立ちます（ただし、\(\mathrm{mex}\) はその集合に含まれない最小の非負整数を表します）。 よって、もし \(n \not\in \mathcal{S}\) であれば、\(n\) 以下の \(\mathcal{S}\) の要素のうち最大のものを \(\bar{n}\) とおくと、

\[g(n) = h(n) = n - \bar{n} + h(\bar{n}) \tag{1}\]

が成り立ちます。 すべての \(n \in \mathcal{S}\) について \(g(n), h(n)\) が求まっていれば、 (1) によって、所望の 非負整数 \(n\) に対して \(g(n)\) を \(\mathrm{O}(\log M)\) 時間で求めることができるので、 以下ではすべての \(n \in \mathcal{S}\) について \(g(n), h(n)\) を求める方法を述べます。

\(\mathcal{S}\) の各要素について、小さい要素から順に \(g(\cdot)\) と \(h(\cdot)\) を求めていきます。 いま、\(n \in \mathcal{S}\) を固定し、\(n\) より小さい \(n' \in \mathcal{S}\) については \(g(n'), h(n')\) が既知と仮定して、\(g(n)\) と \(h(n)\) を求めることを考えます。 （つまり、計算済みの値と (1) を用れば、\(g(0), g(1), \ldots, g(n-1)\) と \(h(0), h(1), \ldots, h(n-1)\) の値のうち所望のものを \(\mathrm{O}(\log M)\) 時間で計算できる状態です。）

石の個数がちょうど \(n\) 個の状態から遷移先とすることが禁止されている石の個数の集合 \(\lbrace X_i - Y_i :i \in \lbrace 1, 2, \ldots, M \rbrace, X_i = n\rbrace\) の要素をすべて並べたものを \(f_1, f_2, \ldots, f_K\) とします。

このとき、 \(g(n) = \mathrm{mex}\lbrace g(n') : n' \in \lbrace 0, 1, 2, \ldots, n-1 \rbrace \setminus \lbrace f_1, f_2, \ldots, f_K \rbrace \rbrace\) であるので、

\[g(0), g(1), g(2), \ldots, g(n-1) \tag{2}\]

に各非負整数が現れる回数がわかれば、

\[g(f_1), g(f_2), \ldots, g(f_K)\]

に各非負整数が現れる回数が (2) における出現回数以上かを調べることで 、\(g(n)\) と \(h(n) = \max\lbrace h(n-1), g(n) \rbrace\) が求まります。 したがって、\(\mathcal{S}\) の各要素の \(g(\cdot)\) と \(h(\cdot)\) を求めていく過程で、(2) における各非負整数の分布を連想配列によって保持していれば良いです。 \(1\) 回以上出現するすべての非負整数を連想配列に記録すると、連想配列のエントリ数が巨大になってしまいますが、 \(0, 1, 2, \ldots, h(n-1)\) までの整数は (2) の中に少なくとも \(1\) 回以上は現れることがわかることを考慮すると、 連想配列には (2) の中に \(2\) 個以上出現するもののみ記録すれば十分であり、それによって連想配列のエントリ数を \(O(M)\) に抑えることができます。

以上で、本問題を \(O(N+M\log M)\) 時間で解くことができます。

おまけ： Grundy 数について

本問題の石取りゲームは、

• 不偏ゲーム（各局面でとることができる選択肢は両プレイヤーで共通）
• 各局面における選択肢の個数は有限
• 必ず有限の手数で終了する
• 正規形（先に、手を打つことができなくなったプレイヤーが負け）

という性質を持っています。以下、そのような性質を持つゲームを考えます。

ゲームの局面 \(G\) に対する Grundy 数 \(g(G)\) は次のように再帰的に定義されます。

\(G\) から一手で遷移可能な局面の集合が \(\lbrace G_1, G_2, \ldots, G_n \rbrace\) のとき、 \(g(G) := \mathrm{mex}\lbrace g(G_1), g(G_2), \ldots, g(G_n)\rbrace\) 。 ただし、\(\mathrm{mex}\) はその集合に含まれない最小の非負整数を表します。 また、\(G\) から一手で遷移可能な局面が存在しないときは \(g(G) := 0\) とします。

実は、Grundy 数が \(0\) の局面は後手必勝、正の局面は先手必勝です。したがって、与えられた局面においてどちらのプレイヤーに必勝戦略が存在するかを判定するには、その局面の Grundy 数を計算すれば良いです。

ここで、複数のゲームの和（選言和）というものを考えます。 \(n\) 個のゲーム \(G_1, G_2, \ldots, G_n\) の和 \(G_1+G_2+\cdots +G_n\) は下記のゲームとして定義されます。

\(n\) 個のゲーム \(G_1, G_2, \ldots, G_n\) を並べ、両プレイヤーは各手番で \(n\) 個のゲームのうちちょうど \(1\) 個のゲームに対して手を打っていき、先に \(n\) 個のゲームのどれに対しても手を打つことができなくなったプレイヤーの負け。

本問題の石取りゲームは、「山の個数が \(1\) 個のみの石取りゲーム」の \(N\) 個の和と捉えることができます。

Grundy 数の性質として、和ゲームの局面 \(G_1+G_2+\cdots + G_n\) の Grundy 数 \(g(G_1+G_2+\cdots +G_n)\) は各成分の Grundy 数 \(g(G_1), g(G_2), \ldots, g(G_n)\) のビットごとの排他的論理和によって、\(g(G_1+G_2+\cdots + G_n) =g(G_1) \oplus g(G_2) \oplus \cdots \oplus g(G_n)\) と表せることが知られています。

したがって本問題では、\(N\) 個の山それぞれについて「その山 \(1\) 個のみからなる石取りゲーム」の Grundy 数が求まれば、全体の石取りゲームの Grundy 数はそれらの排他的論理和として求まり、それが \(0\) かどうかによってどちらのプレイヤーが勝つかを求めることができます。