博弈论（Nim 与 SG 函数）CSP-S

💡 核心思想

博弈论研究的是两人轮流操作、都采取最优策略时的胜负判定。Nim 游戏是最基础的模型：有若干堆石子，每次可以从一堆中取任意正数个，取最后一颗者胜。SG 函数（Sprague-Grundy）是 Nim 的推广：将任意组合游戏转化为 Nim 堆，异或和为 0 则先手必败，否则先手必胜。

🎯 直觉理解

想象你在玩"取石子"游戏。如果只剩一堆 5 个石子，你先手拿几个？答案是拿 5 个，直接赢。如果有两堆各 3 个，这就是 Nim 的经典平衡态：无论先手怎么拿，后手都能镜像操作保持平衡，最后后手赢。SG 函数就是给每种"局面"打分，分数为 0 表示必败，非 0 表示必胜。

📝 算法流程

1. Nim 游戏：计算所有堆的石子数异或和，为 0 则先手必败
2. SG 函数定义：sg(x) = mex{ sg(y) | 从 x 可以一步到达 y }
3. mex：最小的非负整数不在后继状态的 SG 集合中
4. 组合游戏：总 SG = sg1 ⊕ sg2 ⊕ ... ⊕ sgn，为 0 则必败
5. 常见模型的 SG 值：单堆取 1~k 个 → sg(x) = x % (k+1)

$$\text{Nim 胜负：} XOR = a_1 \oplus a_2 \oplus \dots \oplus a_n,\quad XOR = 0 \Rightarrow \text{必败}$$

$$\text{SG}(x) = \text{mex}\{ \text{SG}(y) \mid y \in \text{next}(x) \}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

// 1. Nim 游戏：判断先手是否必胜
bool nimWin(vector& a) {
    int x = 0;
    for (int v : a) x ^= v;
    return x != 0; // 异或和不为 0 则先手必胜
}

// 2. SG 函数（以"每次取 1~3 个"为例）
int sg[1005];
bool vis[1005];

void calcSG(int n, int maxTake) {
    sg[0] = 0; // 0 个石子必败
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        for (int j = 1; j <= maxTake && i - j >= 0; j++)
            vis[sg[i - j]] = true;
        for (int j = 0; ; j++)
            if (!vis[j]) { sg[i] = j; break; }
    }
}

int main() {
    vector piles = {3, 4, 5};
    cout << (nimWin(piles) ? "First wins" : "Second wins") << endl;
    
    calcSG(20, 3);
    for (int i = 0; i <= 10; i++) cout << "sg(" << i << ")=" << sg[i] << " ";
    cout << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目