P-position 和 N-position 的差別：一個是「你走完就輸了」，另一個是「輪到你就贏了」。
兩種局面
所有公平博弈（兩人輪流、完全資訊、最後無法操作者輸）都可以把每個局面分成兩類：
- P-position（Previous player wins）：剛走完那個人贏——也就是輪到你時必輸
- N-position（Next player wins）：輪到你走時必贏
分析規則：
終止狀態（無法操作）= P-position
能走到至少一個 P-position 的局面 = N-position（選那一步）
只能走到 N-position 的局面 = P-position（無論怎麼走對手都有好手）
Nim 遊戲：XOR 決定一切
多堆石子，每次從一堆取任意數量（至少 1 個），取最後一個的人贏。
Bouton 定理（1902）：
所有堆數量的 XOR = 0 → P-position（後手必勝）
所有堆數量的 XOR ≠ 0 → N-position（先手必勝）
例：[3, 5, 6]
3 ^ 5 ^ 6 = 011 ^ 101 ^ 110 = 000 = 0 → 後手必勝
例：[1, 2, 3]
1 ^ 2 ^ 3 = 001 ^ 010 ^ 011 = 000 = 0 → 後手必勝
為什麼 XOR？XOR = 0 代表「各位都平衡」。先手任何一步都會打破平衡（讓 XOR ≠ 0）；後手總能恢復平衡（讓 XOR = 0）。當所有堆都是 0，後手贏。
Sprague-Grundy 定理：任何博弈都等價於 Nim
每個博弈狀態有一個 Grundy 數（g 值，也叫 nim-value）：
g(狀態) = mex({g(所有後繼狀態)})
mex = minimum excludant = 不在集合中的最小非負整數
mex({0, 1, 2}) = 3
mex({0, 2}) = 1
mex({}) = 0 ← 終止狀態
g = 0 → P-position（必輸）
g ≠ 0 → N-position（必勝）
組合博弈（多個子遊戲同時進行）的整體 Grundy 數 = 各子遊戲 Grundy 數的 XOR。
這讓你能把一個複雜博弈分解成子遊戲，各自計算 g 值，XOR 後判斷整體勝負。
競程常見快捷結論
一堆，每次取 1 到 k 個：n % (k+1) == 0 → P-position
Staircase Nim（樓梯取石子）：只有奇數層的石子決定勝負，等同對奇數層做 Nim
多組詢問的 Nim：大量詢問前，找 g 值的規律（通常有週期性）
Sprague-Grundy 定理說，你不需要對每種博弈重新分析——它們都是 Nim 的偽裝版。