HDU 1849 Rabbit and Grass 完整解析

1×N 棋盤，M 個棋子可重疊放置。雙方輪流將任一棋子向左移動任意距離（不超出邊界）。所有棋子移至 0 號格時遊戲結束，最後移動者勝。Rabbit 先手，輸出勝負。

核心洞察：獨立子遊戲的 Nim 和

每個棋子獨立構成一個子遊戲：位置 k 的棋子等價於大小為 k 的 Nim 堆。移動棋子從 k 到 j (j < k) 等價於從大小 k 的堆取走 k-j 個石子。多棋子疊放互不影響（各自獨立）。

根據 Sprague-Grundy 定理，總遊戲 SG 值 = 所有棋子位置異或和：

SG = k₁ ⊕ k₂ ⊕ ... ⊕ kₘ

SG ≠ 0 ⇒ 先手必勝（Rabbit Win!），SG = 0 ⇒ 先手必敗（Grass Win!）

完整 AC 程式碼

#include <cstdio>

int main() {
    int m;
    while (scanf("%d", &m) == 1 && m) {
        int xorsum = 0;
        for (int i = 0; i < m; i++) {
            int pos;
            scanf("%d", &pos);
            xorsum ^= pos;
        }
        puts(xorsum ? "Rabbit Win!" : "Grass Win!");
    }
    return 0;
}

範例驗證

輸入：
2
3 5
3
3 5 6
0

輸出：
Rabbit Win!  (3⊕5=6≠0)
Grass Win!   (3⊕5⊕6=0)

關鍵點總結

• 棋子疊放不影響：各棋子獨立，位置相同仍各自計入異或
• 棋盤大小 N 無關：只要初始位置合法，N 不參與計算
• M=0 結束輸入：不作為測資處理
• 經典 Nim 變體：一維棋子左移遊戲 = Nim 遊戲