\(N\) 回の操作後、皿 \(i\) にあるコインの個数を \(x_i\) と書くことにします。 詳細は省きますが、\(\oplus x_i\) が \(0\) かどうかだけが重要です。ここで \(\oplus\) はビットごとの排他的論理和を表します。

\(N\) の偶奇によって、それぞれのプレイヤーの目的が変化します。

• 奇数のとき：先手は \(\oplus x_i\) が \(0\) になるように、後手は \(\oplus x_i\) が \(0\) にならないように手を打ちます。
• 偶数のとき：先手は \(\oplus x_i\) が \(0\) にならないように、後手は \(\oplus x_i\) が \(0\) になるように手を打ちます。

まず、\(N\) が偶数のときについて説明します。 任意の整数 \(n\) について \(n\) 個のコインが入った袋が偶数個あるとき、後手必勝です。 なぜなら、後手は先手が打った手と対称な手を打ち続けることができ、\(\oplus x_i\) が後手の操作後に常に \(0\) に保つことができるためです。 一方、それ以外の場合では先手必勝です。 なぜなら、先手は「最も多くのコインが乗った皿と最も多くのコインが入った袋を選ぶ」という手を繰り返すことで、過半数のコインが一つの皿に乗っている状態にできます。これにより、先手は \(\oplus x_i\) が \(0\) にならないようにすることが必ずできます。

次に、\(N\) が奇数のときについて説明します。 先程の場合とほぼ同様、後手は「最も多くのコインが乗った皿と最も多くのコインが入った袋を選ぶ」という手を繰り返すことで過半数のコインが一つの皿に乗っている状態にできることがわかります。よって、\(N\) が奇数のときは後手必勝です。

上記の判定は \(O(N \log N)\) で実行可能で十分高速です。