HDU 1536 S-Nim：SG 函數解決受限取石子遊戲

題目大意

經典 Nim 遊戲變體：每次只能取 S 集合中指定數量的石子。給定多堆石子，判斷先手勝負。多組測試，每組多個詢問。

SG 函數理論

• 單堆 SG 值：`sg[x] = mex{ sg[x - s] | s ∈ S, x ≥ s }`。
• 多堆組合：所有堆 SG 值異或和 ≠ 0 先手勝 (W)，否則負 (L)。
• 預計算 `sg[0..10000]` (石子數上限)。

代碼實現 (C++)

#include 
#include 
#include 
using namespace std;

const int MAXH = 10005;
int S[105], sg[MAXH];
bool vis[MAXH];

void computeSG(int k) {
    memset(sg, 0, sizeof(sg));
    for (int i = 1; i < MAXH; i++) {
        memset(vis, 0, sizeof(vis));
        for (int j = 0; j < k; j++) {
            if (i >= S[j]) vis[sg[i - S[j]]] = true;
        }
        for (int j = 0; ; j++) if (!vis[j]) { sg[i] = j; break; }
    }
}

int main() {
    int k;
    while (~scanf("%d", &k) && k) {
        for (int i = 0; i < k; i++) scanf("%d", &S[i]);
        computeSG(k);
        int m; scanf("%d", &m);
        string ans;
        while (m--) {
            int l; scanf("%d", &l);
            int xorsum = 0;
            while (l--) { int h; scanf("%d", &h); xorsum ^= sg[h]; }
            ans += (xorsum ? 'W' : 'L');
        }
        printf("%s\n", ans.c_str());
    }
    return 0;
}

關鍵點

• SG 值計算上限 10000 足夠覆蓋題目約束 (h_i ≤ 10000)。
• `vis` 數組大小設為 MAXH 即可，因 SG 值不超過可達狀態數。
• 多詢問共享同一 S 集合的 SG 表，只需預計算一次。
• 輸出每組測試一行字符串 (如 `LWW`)，無空格。

複雜度

• 預計算 SG：O(k * MAXH) ≈ 100 * 10000 = 1e6。
• 查詢：O(總堆數)。
• 整體極快，適合多測試用例。