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 值的規律（通常有週期性）其中一個漂亮到不像博弈題的是 Wythoff’s Game：兩堆石子，每次可以從一堆取任意個，或兩堆各取相同數量。它的 P-position 直接被黃金比例 φ = (1+√5)/2 鎖死：
第 k 組 P-position = (⌊k·φ⌋, ⌊k·φ²⌋)
k = 0,1,2,... → (0,0), (1,2), (3,5), (4,7), (6,10), ...判斷一個局面 (a, b)（設 a ≤ b）是不是必敗，不用建表——算 k = b − a，若 ⌊k·φ⌋ == a 就是 P-position。石子博弈的答案落在無理數上，第一次看到都會愣一下。
當狀態沒有公式：Minimax 硬搜
XOR 和 Grundy 數是「有結構的博弈」的捷徑。但很多遊戲（井字棋、一般棋局）找不到這種漂亮公式，那就退回最樸素的辦法——把博弈樹整棵搜出來，我取極大、對手取極小：
int minimax(int state, boolean isMax) {
if (isTerminal(state)) return evaluate(state);
int best = isMax ? Integer.MIN_VALUE : Integer.MAX_VALUE;
for (int next : getMoves(state)) {
int val = minimax(next, !isMax);
best = isMax ? Math.max(best, val) : Math.min(best, val);
}
return best;
}樸素 Minimax 會把整棵樹走完，狀態一多就爆。實務上一定配 Alpha-Beta 剪枝——記住「目前已知的上下界」，一旦發現某分支不可能比現有選擇更好就直接砍掉，能省下大半搜尋空間。這也是為什麼 Grundy 數值得學：能化約成 Nim 的博弈，你連樹都不用搜，一個 XOR 就出答案。
🎬 互動視覺化：博弈與雜項演算法動畫 — 看 Nim 局面的 XOR 怎麼隨每一步變化、必勝方永遠能把它扳回 0，以及 Grundy 數怎麼從終止狀態往回一格格 mex 出來。
Sprague-Grundy 定理說，你不需要對每種博弈重新分析——它們都是 Nim 的偽裝版。
接下來往哪走
- FFT 快速傅立葉變換：O(n²) 乘法變 O(n log n) — 下一篇：競程數學的另一座山
- Bit Manipulation 位元運算 — Nim 的勝負判斷靠 XOR，位元運算的直覺從這裡建
- 進階 DP：當狀態不再是一個數字 — 算 Grundy 數的 mex 遞推本質上就是狀態 DP