S-Nim：SG 函數解多堆取石子遊戲

問題描述

經典 Nim 遊戲變體：每回合只能從一堆中取走屬於集合 S 的石子數（S 大小 k ≤ 100，元素 ≤ 10000）。給定多組查詢，每組包含 l (≤100) 堆，每堆石子數 h_i (≤10000)。判斷先手勝 (W) 或負 (L)。

SG 函數理論

每堆獨立遊戲，SG 值定義為：sg[x] = mex{ sg[x - s] | s ∈ S, s ≤ x }。多堆合併：總 SG = 所有堆 SG 異或和。總 SG ≠ 0 為先手勝 (W)，否則負 (L)。

算法流程

1. 預處理：對每個測試案例的集合 S，計算 sg[0..max_h]（max_h = max(h_i)）。用遞歸 + 記憶化或迭代 DP。
2. 對每組查詢，異或所有堆的 sg[h_i]，輸出結果。

複雜度

預處理 O(max_h * k)，max_h ≤ 10000, k ≤ 100 → 10⁶ 操作。查詢 O(l)。多案例累計極快。

參考代碼 (C++)

#include 
using namespace std;
const int MAXH = 10005;
int S[105], sg[MAXH];
bool vis[105];
int k;

int getSG(int x) {
    if (sg[x] != -1) return sg[x];
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < k; ++i) {
        if (x >= S[i]) vis[getSG(x - S[i])] = true;
    }
    for (int i = 0; ; ++i) if (!vis[i]) return sg[x] = i;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> k, k) {
        for (int i = 0; i < k; ++i) cin >> S[i];
        sort(S, S + k);
        memset(sg, -1, sizeof(sg));
        sg[0] = 0;
        int m; cin >> m;
        while (m--) {
            int l; cin >> l;
            int xorsum = 0;
            while (l--) {
                int h; cin >> h;
                xorsum ^= getSG(h);
            }
            cout << (xorsum ? 'W' : 'L');
        }
        cout << '\n';
    }
    return 0;
}

關鍵點

• SG 函數將複雜遊戲分解為獨立子遊戲，異或合併。
• mex（最小未出現非負整數）計算核心。
• 記憶化遞歸避免重複計算，sg[0]=0 為基礎情況。
• 集合 S 需排序（雖非必需），便於理解。

總結

• 組合遊戲理論經典應用：S-Nim 通過 SG 函數轉化為 Nim。
• 預處理 SG 表，查詢 O(1) 判斷勝負。
• 注意多測試案例格式：每案例查詢結果連續輸出，案例間換行。