HDU 1850 Being a Good Boy：Nim 博弈計算首步獲勝方案數

問題描述

M 堆撲克牌，每堆 Nᵢ 張。兩人輪流取牌，每次選一堆取任意張（≥1）。取完者勝。輸出先手第一步有多少種獲勝選擇（即選某堆取若干張後，使局面變為必敗態）。

核心理論：Nim 和與獲勝移動

設所有堆數異或和 S = N₁ ⊕ N₂ ⊕ ... ⊕ Nₘ。

• S = 0：先手必敗，方案數 = 0。
• S ≠ 0：先手必勝。在堆 i 取牌後剩餘 left，新 Nim 和 S' = S ⊕ Nᵢ ⊕ left。
  要使 S' = 0，需 left = S ⊕ Nᵢ。
  合法條件：left < Nᵢ（即實際取走 > 0）。

因此，堆 i 提供獲勝第一步 當且僅當 (S ⊕ Nᵢ) < Nᵢ。方案數即滿足此條件的堆數。

代碼實現

#include 
using namespace std;
int m, num[102];
int main() {
    while (cin >> m && m) {
        int s = 0;
        for (int i = 1; i <= m; i++) {
            cin >> num[i];
            s ^= num[i];
        }
        int ans = 0;
        for (int i = 1; i <= m; i++) {
            if (num[i] > (s ^ num[i])) // 注意括號！^ 優先級低於 >
                ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

關鍵細節

1. 運算符優先級陷阱：C++ 中 ^（異或）優先級低於 >（比較）。
   num[i] > s ^ num[i] 等價於 (num[i] > s) ^ num[i] → 錯誤！
   必須寫成 num[i] > (s ^ num[i])。
2. 輸入結束：m = 0 結束。
3. 數據範圍：M ≤ 100, Nᵢ ≤ 1,000,000，int 足夠。

樣例驗證

輸入：3 5 7 9

• S = 5 ⊕ 7 ⊕ 9 = 11（非零）。
• 堆 5: 11 ⊕ 5 = 14 > 5 ✗
• 堆 7: 11 ⊕ 7 = 12 > 7 ✗
• 堆 9: 11 ⊕ 9 = 2 < 9 ✓

方案數 = 1，符合樣例輸出。

總結

HDU 1850 是 Nim 博弈「計算首步獲勝方案數」的標準應用：

1. 計算總異或和 S。
2. 若 S=0 輸出 0。
3. 否則統計滿足 Nᵢ > (S ⊕ Nᵢ) 的堆數。
4. 牢記異或優先級低於比較，必須加括號。

此題與 HDU 2176（輸出具體方案）是姊妹題，共同覆蓋 Nim 博弈的判定與構造兩大核心需求。