LightOJ 1199 Partitioning Game - SG 函數與博弈論完整解析

遊戲規則建模

• n 堆石子，第 i 堆 aᵢ 個（1 ≤ aᵢ ≤ 10,000）。
• 每回合玩家選一堆，分成兩堆數量不同的石子（即分成 x 和 y，x+y=a, x≠y, x,y≥1）。
• 無法操作者輸。雙方最優策略，求先手勝負。

SG 函數定義與遞推

單堆遊戲獨立，整體 SG = 所有堆 SG 異或和。
sg[x] = mex{ sg[y] ^ sg[x-y] | 1 ≤ y < x/2 }（利用 x≠y 對稱性，只枚舉 y < x/2）。
基礎情況：sg[1]=sg[2]=0（無法分割）。

預計算 SG 表（離線 O(MAX_A²) → 優化至 O(MAX_A log MAX_A)）

const int MAXA = 10000;
int sg[MAXA + 1];
bool vis[MAXA + 1];

void calcSG() {
    sg[1] = sg[2] = 0;
    for (int x = 3; x <= MAXA; ++x) {
        fill(vis, vis + MAXA + 1, false);
        for (int y = 1; y < (x+1)/2; ++y)  // y < x-y 保證不等
            vis[sg[y] ^ sg[x-y]] = true;
        for (int g = 0; ; ++g)
            if (!vis[g]) { sg[x] = g; break; }
    }
}

優化觀察：sg[x] 增長極慢（實測最大值 < 20），vis 數組可縮小至 32 或 64，大幅加速。

判斷勝負

int main() {
    calcSG();
    int T; scanf("%d", &T);
    for (int cs = 1; cs <= T; ++cs) {
        int n; scanf("%d", &n);
        int xorsum = 0;
        for (int i = 0, a; i < n; ++i) {
            scanf("%d", &a);
            xorsum ^= sg[a];
        }
        printf("Case %d: %s\n", cs, xorsum ? "Alice" : "Bob");
    }
    return 0;
}

SG 值規律探索（可選加分項）

打印前 100 個 SG 值可發現：
sg[1]=0, sg[2]=0, sg[3]=1, sg[4]=1, sg[5]=2, sg[6]=2, sg[7]=3, sg[8]=3...
規律：sg[2k] = sg[2k+1] = k-1（k≥1）。
證明可用數學歸納法，掌握後可 O(1) 計算 SG，無需預計算表。

複雜度

• 預計算：O(MAX_A² / 4) ≈ 2.5×10⁷，配合 vis 縮小極快（< 0.1s）。
• 每測試用例：O(n)。
• 空間：O(MAX_A)。

核心模板總結

// 通用 SG 模板
int sg[MAX_STATE];
bool vis[MAX_SG];
void getSG() {
    sg[terminal] = 0;
    for (state = terminal+1; state <= MAX_STATE; ++state) {
        clear(vis);
        for (next : moves(state)) vis[sg[next]] = true;
        sg[state] = mex(vis);
    }
}