問題
石の山が $N$ 個あり、$i$ 番目の山には $a_i$ 個の石がある。先手・後手が交互に、次のどちらかの操作を 1 回行う。
- (取る) 1 つの山を選び、1 個以上の石を取り除く（山が空になってもよい）
- (分ける) 1 つの山を選び、それを 2 つの 空でない 山に分ける（石の総数は変わらない）
操作できなくなった（石が 1 個も無い）方が負け。両者が最善を尽くすとき、先手が勝つなら First、後手が勝つなら Second を出力せよ。
入力形式
N
a_1 a_2 ... a_N制約
| # | 条件 |
|---|---|
| 1 | $1\le N\le 2\times10^5$ |
| 2 | $1\le a_i\le 10^{18}$ |
| 3 | 入力はすべて整数 |
入出力例
入力例1
3
1 2 3出力例1
First（通常の Nim なら $1\oplus2\oplus3=0$ で後手の勝ち。ここでは 3 の山を「1 つ取り除いて 2」にしたり「1 と 2 に分けて」にできるので事情が違う）
入力例2
2
3 4出力例2
First（4 の山から 1 個取って $(3,3)$ にすれば、後手が何をしても先手が同じ操作を返せる）
入力例3
2
5 5出力例3
Second背景と出典
「取る」に加えて「分ける」を許す Nim は Lasker's Nim と呼ばれる。私の記憶では Winning Ways（Berlekamp–Conway–Guy）にあり、考案者は世界チャンピオンのエマヌエル・ラスカーとされるが、本セッションでは文献を開いておらず、帰属は未確認。正しさの根拠は下の検証ログ（単山の mex 表との照合と、全状態の全探索との照合）で、証明は本ファイルでは示していない。
Sprague–Grundy の定理（独立な部分ゲームの和は、各 Grundy 数の XOR が 0 のとき後手必勝）は標準的な結果。この問題の価値は、定理を使う前の「単山の Grundy 数 $g(n)$ を実際に表にして規則を見つける」という手作業にある。
概念図
ヒント（クリックで段階的に開示）
ヒント1（方向性）
山は互いに独立で、1 手は 1 つの山にしか触らない。単山 1 個の Grundy 数 $g(n)$ が分かれば、全体は $g(a_1)\oplus\cdots\oplus g(a_N)$ が 0 かどうかで決まる。「分ける」手の行き先は 2 つの山の和ゲームなので、その Grundy 数は $g(p)\oplus g(n-p)$。
ヒント2（アプローチ）
$g(n)=\operatorname{mex}\bigl(\{g(m): 0\le m<n\}\cup\{g(p)\oplus g(n-p): 1\le p\le n/2\}\bigr)$ を $n\le 20$ ほどまで手元のコードで表にする。通常の Nim なら $g(n)=n$ になるはずなのに、ある $n$ だけずれる。
ヒント3（誘導）
$g(0..12)=0,1,2,4,3,5,6,8,7,9,10,12,11$。$n\bmod4$ で見ると、$n\bmod 4=3$ のとき $n+1$、$n\bmod4=0$（$n>0$）のとき $n-1$、それ以外は $n$。あとは XOR を取るだけ。
模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
x = 0
for i in range(n):
a = int(data[1 + i])
r = a & 3
if r == 3:
g = a + 1 # 4k+3 -> 4k+4
elif r == 0 and a > 0:
g = a - 1 # 4k+4 -> 4k+3（a>0 の 4 の倍数）
else:
g = a # 4k+1, 4k+2 はそのまま
x ^= g
print("First" if x else "Second")
main()計算量: $O(N)$。実測（Python 3.14.7、M1 Mac）で $N=2\times10^5$、$a_i\le10^{18}$ のランダム入力が 0.07 s（起動込み）。
Step-by-Step 解説
山 $n$ から「$p$ と $n-p$ に分ける」と、盤面は「山 $p$」と「山 $n-p$」の 2 つの独立ゲームの和になる。和の Grundy 数は XOR なので、1 手の行き先の Grundy 数は $g(p)\oplus g(n-p)$。したがって単山の定義は上のヒント2の mex で閉じる。全体の盤面は各山の $g$ の XOR で決まる（Sprague–Grundy）。
$g(1)=1,\ g(2)=2$ まではそのまま。$n=3$ では行き先に $g(0),g(1),g(2)=0,1,2$ と分割 $(1,2)$ の $1\oplus2=3$ があるので mex は 4。$n=4$ では行き先に $0,1,2,4$（$g(3)=4$）と分割 $(1,3)$ の $1\oplus4=5$、$(2,2)$ の $0$ があり、$3$ だけ欠けているので $g(4)=3$。以降 4 個ずつ同じ形で、$g(4k+3)=4k+4,\ g(4k+4)=4k+3$。**$g$ は自然数の置換**になる（ずれるのは隣り合う 2 値の入れ替えだけ）。
$n\le3000$ のすべてで mex を実際に計算した表と上の式が一致した（実測）。さらに石の総数 14 以下の全 507 状態（山の多重集合）を状態の全探索（山を取る・分ける全手の再帰）で解き、$g$ の XOR による判定と全件一致した（実測）。ただし $n>3000$ の規則は この実測からの外挿で、帰納法の証明は本ファイルに書いていない。
通常の Nim の判定 $\bigoplus a_i$ だと 507 状態中 37 状態で誤る（実測）。3 と 4 の入替を忘れて「$4k+3\to4k+4$」だけ直すと 23 状態で誤る（実測。$4k+4$ 側を直し忘れると、入力例 2 の $(3,4)$ が $4\oplus4=0$ で Second になる）。
迷った他案と採らなかった理由
| 案 | 計算量 | 採否 | 理由 |
|---|---|---|---|
| 山の多重集合に対する状態の全探索 | 指数 | 検算用のみ | 総数 14 まででも全 507 状態。$N=2\times10^5$ には不可 |
| 通常 Nim の XOR | $O(N)$ | 不採用 | 「分ける」手を無視している。507 状態中 37 状態で誤答 |
| 山ごとに mex の表を作る | $O(a^2)$ / 山 | 規則の発見用のみ | $a\le10^{18}$ には不可。ただし規則を見つける手段としては必要 |
| $g(n)$ の閉形式（本解） | $O(1)$ / 山 | 採用 | 表の全 3001 値・全 507 状態と一致。証明は未了 |
前提が変わったら:
- 「分ける」を 3 つ以上に許すと別のゲーム。単山の mex を再計算して規則を探し直す（本解の式は使えない）
- 「分ける」だけで「取る」が無い（Grundy's game 系）は規則が周期的でなく、既知の Grundy 数の列が不規則に見える。本問のように閉形式には落ちない
- 勝ち手を出力させるなら、山 $i$ の目標値 $t=g(a_i)\oplus X$ に対し、取る手は $g^{-1}(t)<a_i$ なら 1 手。分ける手の探索は $O(a_i)$ になるので、$a_i$ が大きいときは別の工夫が要る（本問では扱わない）
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 通常 Nim の XOR で判定する | 「分ける」手の存在を落とす | $g$ に変換してから XOR（37/507 状態で誤答） |
| $4k+3$ だけ $+1$ にして $4k+4$ を直さない | 入れ替えが 2 つ組であることを見落とす | $a\bmod4=0$（$a>0$）なら $a-1$（23/507 状態で誤答） |
| $a=0$ に $-1$ を適用する | 「4 の倍数」に 0 を含めてしまう | r == 0 and a > 0（本問は $a_i\ge1$ だが、拡張時に効く） |
| 規則を表で確かめず公式だけ暗記する | 出典を開かずに「Lasker's Nim は $n\bmod4$」と覚える | $n\le20$ を自分で表にして、式がその表と合うかを見る |
次のステップ
- 発展1: 「取る」を 1 手で最大 $k$ 個に制限した版（Lasker 型と Moore 型の合成）の $g(n)$ を表で調べる
- 発展2: $g(4k+3)=4k+4,\ g(4k+4)=4k+3$ を帰納法で証明する（鍵は「$g(p)\oplus g(q)$ が $p+q=n$ のとき自分自身 $g(n)$ にならない」こと。奇偶と下位 2 ビットで場合分けする）
- 次回予告: 焦点帯 M1 の別のゲーム、または DP の高速化
検証ログ（本セッションで実行した数値）
- 単山の mex 表との照合（実測）: 「取る」「分ける」の全手から mex を計算した $g(0..3000)$ と式が全 3001 値で一致（不一致 0）
- 全状態の全探索との照合（実測）: 石の総数 1〜14 の山の多重集合 507 状態を再帰で解き、$g$ の XOR 判定と全件一致。後手必勝は 61 状態。プログラム全体（標準入力経由）は 507 状態から無作為に取った 300 状態で全件一致
- 誤った方法（実測）: 通常 Nim の XOR 37/507、$4k+3$ だけ直す 23/507 で誤答
- 入力例（実測）: 例 1
First、例 2First、例 3Second - 実行時間（実測）: $N=2\times10^5$、$a_i\le10^{18}$ で 0.07 s
- 扱っていない範囲: $n>3000$ の規則の証明、勝ち手の出力、「分ける」を 3 つ以上にした版、Lasker・Winning Ways の原典確認