問題
$N$ 段の階段があり、段には下から $1,2,\dots,N$ の番号がついている（段 $0$ は地面）。段 $i$ には硬貨が $a_i$ 枚ある。
先手と後手が交互に次の操作を行う。
硬貨が 1 枚以上ある段 $i$（$1\le i\le N$）を 1 つ選び、そこから $k$ 枚（$1\le k\le a_i$）を 1 つ下の段 $i-1$ へ移す。段 $0$（地面）に落ちた硬貨はもう動かせない。
操作できなくなった（すべての硬貨が地面にある）人の負けとする。
両者が最善を尽くすとき、先手が勝つなら First、負けるなら Second を 1 行目に出力せよ。2 行目には、先手の初手のうち、そのあと先手が必ず勝てる手の数（段 $i$ と枚数 $k$ の組の個数）を出力せよ。先手が負ける場合は 0 を出力する。
入力形式
N
a_1 a_2 ... a_N制約
| # | 条件 |
|---|---|
| 1 | $1\le N\le 2\times10^5$ |
| 2 | $0\le a_i\le 10^9$ |
| 3 | 入力はすべて整数 |
入出力例
入力例1
3
2 1 3出力例1
First
2（奇数段の XOR は $a_1\oplus a_3=2\oplus3=1$。勝ち手は「段 3 から 1 枚降ろす（$3\to2$、XOR が 0 に）」と「段 2 から段 1 へ 1 枚移す（$a_1$ が $2\to3$、XOR が 0 に）」の 2 つ）
入力例2
4
1 5 1 2出力例2
Second
0（段 2 に 5 枚もあるのに後手必勝。奇数段 $a_1\oplus a_3=1\oplus1=0$ だけで決まる）
入力例3
5
3 1 4 1 5出力例3
First
1背景と出典
階段 Nim（Staircase Nim）は組合せゲーム理論の定番の例で、Berlekamp・Conway・Guy『Winning Ways for your Mathematical Plays』（1982）などで扱われる。本セッションでは原典を参照しておらず、勝敗条件と勝ち手の数え方は 全局面探索（$N\le5$、$a_i\le3$ の 1364 局面）と照合 して確かめた。
概念図：奇数段だけが Nim の山、偶数段は在庫
ヒント（クリックで段階的に開示）
ヒント1（方向性）
偶数段の硬貨は「動かしても、相手がすぐ同じ枚数をもう 1 段下へ動かせば元に戻せる」。つまり勝敗に効かない。では勝敗を決めているのはどの段か。
ヒント2（アプローチ）
奇数段 $i$ から段 $i-1$（偶数段か地面）へ $k$ 枚移すのは、奇数段だけを見れば Nim の山 $a_i$ から $k$ 枚取る のと同じ。よって奇数段 $a_1,a_3,a_5,\dots$ の XOR $X$ が 0 なら後手必勝。
ただし勝ち手を数えるときは、偶数段 $i+1$ から奇数段 $i$ へ移す手（Nim で言えば 山を増やす手）も勝ち手になりうることに注意。
ヒント3（誘導）
$X\ne0$ のとき、奇数段 $i$ ごとに目標 $t=a_i\oplus X$ を計算する。
- $t<a_i$ なら「段 $i$ から $a_i-t$ 枚降ろす」が勝ち手
- $t>a_i$ かつ $t-a_i\le a_{i+1}$（段 $i+1$ が存在）なら「段 $i+1$ から $t-a_i$ 枚を段 $i$ へ」が勝ち手
x = XOR(a[1], a[3], a[5], ...)
for i in 奇数段:
t = a[i] ^ x
if t < a[i]: cnt += 1
if i+1 <= N and t > a[i] and t - a[i] <= a[i+1]: cnt += 1模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [0] + list(map(int, data[1:1 + n])) # a[i] = 段 i の硬貨（段 0 は地面）
x = 0
for i in range(1, n + 1, 2): # 奇数段だけの XOR
x ^= a[i]
if x == 0:
print("Second")
print(0)
return
cnt = 0
for i in range(1, n + 1, 2):
t = a[i] ^ x
if t < a[i]: # 奇数段 i から a[i]-t 枚降ろす
cnt += 1
if i + 1 <= n and t > a[i] and t - a[i] <= a[i + 1]:
cnt += 1 # 偶数段 i+1 から t-a[i] 枚を奇数段 i へ
print("First")
print(cnt)
main()計算量: $O(N)$。実測で $N=2\times10^5$、$a_i\le10^9$ のランダム入力が 0.22 s（Python 3.14.7、M1 Mac。以下の実測も同じ環境）。
Step-by-Step 解説
後手（負けている側）が奇数段の XOR を 0 に保つ戦略を持っているとする。相手が 偶数段 $2j$ から段 $2j-1$ へ $k$ 枚 移したら、こちらは 段 $2j-1$ から段 $2j-2$ へ同じ $k$ 枚 移す。奇数段 $2j-1$ の枚数は元に戻り、XOR も 0 のまま。
この「真似」はいつでも可能（直前に $k$ 枚増えたので $k$ 枚ある）。硬貨は下にしか動かないのでゲームは必ず終わり、真似で負けることはない。
奇数段 $2j-1$ から $k$ 枚を段 $2j-2$ へ移すと、奇数段だけ見れば山 $a_{2j-1}$ が $k$ 減る。移った先は偶数段（または地面）なので、奇数段の山には入らない。
よって奇数段の山だけの Nim として、Bouton の定理（XOR が 0 なら後手必勝）がそのまま使える。
先手の勝ち手は「手のあと奇数段の XOR が 0 になる手」とちょうど一致する（0 を渡せば Step 1・2 の戦略で勝てる。0 以外を渡すと相手がまた 0 を返せる）。
奇数段 $i$ の枚数を $a_i$ から $t$ に変えて XOR を 0 にするには $t=a_i\oplus X$ が必要（他の山は変えない）。変え方は 2 通り:
| 変え方 | 条件 | 動かす硬貨 |
|---|---|---|
| 減らす | $t<a_i$ | 段 $i$ から $a_i-t$ 枚を下へ |
| 増やす | $t>a_i$ かつ $t-a_i\le a_{i+1}$ | 段 $i+1$（偶数段）から $t-a_i$ 枚を段 $i$ へ |
偶数段 $i+1$ から段 $i$ へ動かす手は 1 つの奇数段しか変えないので、他の組み合わせは無い。
普通の Nim では $t>a_i$（増やす）は不可能なので勝ち手は「$a_i\oplus X<a_i$ となる山の数」だけ。階段 Nim では 偶数段が「山を足す」在庫 になる。入力例 1 の「段 2 → 段 1 に 1 枚」がそれに当たる。
これを数え忘れた版は、全局面 1364 のうち 506 局面で勝ち手の数を誤った（実測）。
XOR 1 回と奇数段ごとに定数回の判定で $O(N)$。$a_i\le10^9$ でも Python の整数でそのまま扱える。
迷った他案と採らなかった理由
| 案 | 計算量 | 採否 | 理由 |
|---|---|---|---|
| 全局面の Grundy 数を DP | 状態数 $\prod(a_i+1)$ | 検算用のみ | $N=5$、$a_i\le3$ で 1024 状態が限界。本番の制約では不可能 |
| 全段の XOR で判定 | $O(N)$ | 不採用 | 全局面 1364 のうち 510 局面で勝敗を誤る（実測）。入力例 2 がそれ |
| 偶数段の XOR で判定 | $O(N)$ | 不採用 | 1364 局面中 513 局面で誤る（実測）。「地面が段 0＝偶数」なので、奇数段から落とす手が Nim の取る手になる |
| 奇数段 XOR（本解） | $O(N)$ | 採用 | 全局面と一致 |
前提が変わったら:
- 1 回に 2 段下まで動かせる（$i\to i-1$ または $i\to i-2$）なら、Step 1 の「真似」が 1 段ずれて成り立たなくなり、本解の偶奇の議論はそのままでは使えない（本セッションでは正しい条件を調べていない）
- 地面が段 1（段 1 から先に動かせない）なら、偶奇が入れ替わり「偶数段の XOR」が正しくなる。段の番号の付け方を問題文でよく確かめる
- 木の上の階段 Nim（各頂点の硬貨を親へ動かす、根が地面）なら、Step 1・2 と同じ議論で「根からの深さが奇数の頂点の XOR」になるはず（本セッションでは全探索で確かめていない）
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 全段の XOR で判定 | 階段を普通の Nim と見てしまう | 奇数段 $1,3,5,\dots$ だけの XOR（全段 XOR は 1364 局面中 510 局面で誤る） |
| 勝ち手を「$a_i\oplus X<a_i$ の奇数段の数」だけ数える | 偶数段から奇数段へ 足す 手を見落とす | $t>a_i$ かつ $t-a_i\le a_{i+1}$ も数える（見落とすと 506 局面で誤る） |
| 段 $N$ が奇数のとき段 $N+1$ を参照 | 配列の範囲外 | i + 1 <= n を先に確かめる |
| 偶数段から「地面」への手を考える | 偶数段 $i\ge2$ の 1 つ下は奇数段。地面に直接落ちるのは段 1 だけ | 移動先は必ず $i-1$ |
次のステップ
- 発展1: 木の上の階段 Nim（AtCoder の「根に向かって石を動かす」型）。深さの偶奇で XOR を取り、勝ち手を辺ごとに数える
- 発展2: 1 回に動かせる枚数が $k$ 枚以下の階段 Nim（各奇数段の山を $\bmod (k+1)$ で見ればよいか、全探索で確かめてから使う）
- 次回予告: 他の山に影響する Nim（Fibonacci Nim のように「取れる数が直前の手に依存する」ゲーム）→ Q2
検証ログ（本セッションで実行した数値）
- 全局面探索との一致（実測）: $N\le4$ の全局面と $N=5$ の 3 割（$a_i\le3$）の計 628 局面で、プログラム全体（標準入出力）の出力 2 行が全局面探索（勝ち手を直接列挙）と全件一致。式だけなら $N\le5$ の全 1364 局面で一致
- 誤りの件数（実測、1364 局面）: 全段 XOR で勝敗判定 → 510 局面で誤り、偶数段 XOR → 513 局面、偶数段からの足す手を数えない → 勝ち手の数が 506 局面で誤り
- 入力例の勝ち手（全探索で列挙）: 例1
[2,1,3]→ (段 2, 1 枚)・(段 3, 1 枚)、例2[1,5,1,2]→ なし、例3[3,1,4,1,5]→ (段 1, 2 枚) - 実行時間（実測）: $N=2\times10^5$、$a_i$ は $[0,10^9]$ の一様乱数で 0.22 s（出力
First/71215） - 扱っていない範囲: 原典（Winning Ways）の記述との照合はしていない。正しさの根拠は上の全局面探索のみ