1×n 棋盤上有 m 個棋子，每步可將任意棋子向左移動任意距離（可重疊），所有棋子移至 0 位置遊戲結束，最後動作者勝。這是經典的階梯尼姆遊戲。
將棋子位置視為「階梯」上的石子。關鍵洞察：
計算所有棋子位置的異或和：
xor_sum = K₁ ⊕ K₂ ⊕ ... ⊕ Kₘ // 其中 Kᵢ 為棋子位置
Case 1: 2子 at 3, 5 → 3⊕5 = 6 ≠ 0 → Rabbit Win! Case 2: 3子 at 3, 5, 6 → 3⊕5⊕6 = 0 → Grass Win!
#include <cstdio>
int main() {
int m, pos;
while (scanf("%d", &m) == 1 && m) {
int xorsum = 0;
for (int i = 0; i < m; ++i) {
scanf("%d", &pos);
xorsum ^= pos;
}
puts(xorsum ? "Rabbit Win!" : "Grass Win!");
}
return 0;
}
這等價於每個棋子獨立構成一個尼姆堆，堆大小 = 位置坐標。移動棋子從位置 x 到 y (y < x) 相當於將尼姆堆從 x 減小到 y。這正是標準尼姆遊戲的操作。
對於 n 級階梯，只有奇數級的石子計入尼姆和。本題棋盤從 0 開始，位置即級數，故直接異或所有位置。
| 變體 | SG 函數 | 獲勝判斷 |
|---|---|---|
| 標準尼姆 | g(x) = x | 異或和 ≠ 0 |
| 階梯尼姆(本題) | g(x) = x (奇數級), 0 (偶數級) | 奇數位置異或和 ≠ 0 |
| Wythoff 遊戲 | g(a,b) = ⌊|a-b|×φ⌋ | 特殊判斷 |
| 取石子遊戲(1..k) | g(x) = x mod (k+1) | 異或和 ≠ 0 |
此題展示了博弈論中 SG 定理的強大威力：複雜的組合遊戲往往歸結為簡單的異或運算。
