HDU 1536 S-Nim：SG 函數與博弈論應用

題目大意

給定 n 個合法取子數 `move[i]`。進行 m 個查詢，每查詢給出 l 堆石子，每堆大小為 `num`。兩人輪流取子，每次從任意一堆取走 `move[]` 中的某個數量，先無法操作者負。判斷先手是否必勝（W）或必敗（L）。

核心理論：SG 函數 (Sprague-Grundy)

• 每堆石子獨立，遊戲為多獨立子遊戲組合
• 單堆 SG 值：`sg[x] = mex{ sg[x - move[i]] }`，其中 `mex` 為最小非負整數
• 整體局面 SG 值 = 所有堆 SG 值異或和
• 總 SG = 0 → 先手必敗 (L)；否則先手必勝 (W)

SG 值計算與周期性優化

題目中石子數上限 10000，直接 DP 計算 `sg[0..10000]` 即可。觀察發現 SG 函數具有周期性（取決於 `move[]` 集合），大數據下可進一步優化，但本題直接預計算足夠。

完整代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 10005;
int n, moves[110];
int sg[MAXN];

void computeSG() {
    bool vis[MAXN];
    sg[0] = 0;
    for (int i = 1; i < MAXN; i++) {
        memset(vis, 0, sizeof(vis));
        for (int j = 0; j < n; j++) {
            if (i >= moves[j]) vis[sg[i - moves[j]]] = true;
        }
        for (int g = 0; ; g++) if (!vis[g]) { sg[i] = g; break; }
    }
}

int main() {
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++) scanf("%d", &moves[i]);
        computeSG();
        
        int m; scanf("%d", &m);
        while (m--) {
            int l; scanf("%d", &l);
            int xorSum = 0;
            while (l--) {
                int x; scanf("%d", &x);
                xorSum ^= sg[x];
            }
            putchar(xorSum ? 'W' : 'L');
        }
        putchar('\n');
    }
    return 0;
}

關鍵點總結

1. SG 函數定義：`mex` 運算核心，表示從該狀態可達到的所有後繼狀態 SG 值中最小的非負整數
2. 異或和性質：多獨立子遊戲組合的 SG 值為各子遊戲 SG 值異或和
3. 預計算優勢：多查詢共用同一 `move[]`，一次預計算 `sg[]` 服務所有查詢
4. 複雜度：預計算 O(MAXN × n)，查詢 O(總堆數)，極快

此題是 SG 函數入門經典題，掌握「單堆 SG 計算 + 多堆異或判斷」模板，可解決大部分取石子類組合博弈問題。