HDU 2176 多堆取石子遊戲：Nim 博弈經典應用

問題描述

m 堆石子，每堆 n[i] 個。兩人輪流從任意一堆取走任意多（≥1）石子，取走最後一顆者勝。給定初始狀態，判斷先手勝負。

Nim 博弈核心定理

先手必勝 ⇔ 所有堆石子數異或和 ≠ 0。
異或和 X = n[1] ⊕ n[2] ⊕ ... ⊕ n[m]。
- X = 0：當前為 P-position（先手必敗，對手有完美策略）。
- X ≠ 0：當前為 N-position（先手有必勝策略）。

必勝策略構造

若 X ≠ 0，找到最高位為 1 的二進制位 k。必存在某堆 n[i] 第 k 位為 1。將該堆改為 n[i] ⊕ X（嚴格小於 n[i]），則新異或和歸零，轉為 P-position。

代碼實現

#include <cstdio>
using namespace std;

int main() {
    int m;
    while (scanf("%d", &m) == 1 && m) {
        int x = 0, val;
        for (int i = 0; i < m; ++i) {
            scanf("%d", &val);
            x ^= val;
        }
        puts(x ? "Yes" : "No");  // 題目輸出格式：先手勝輸出 Yes
    }
    return 0;
}

複雜度

• 時間 O(m) 每測試用例。
• 空間 O(1)。

擴展：誤解釐清

• 非取完即勝：若規則改為取完輸（Misère Nim），僅當所有堆大小均為 1 時策略相反（奇數堆先手輸），其餘同正常 Nim。
• 限制取石數：若每堆最多取 k 顆，則為有限取石遊戲，需用 SG 函數分析，不再是簡單異或。