博弈论（Nim 与 SG 函数）NOI

💡 核心思想

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

🎯 直觉理解

博弈论研究"双方轮流行动、胜负取决于最后一步"的游戏，结论往往出奇简洁。最经典的 Nim 游戏：几堆石子，每次取一堆的任意数量，取完最后一颗的人赢。结论：所有堆的数量异或不为 0 时先手必胜——先手总能把局面变成异或为 0 送给对手。

SG 函数把任意公平游戏归约成 Nim：每个局面的 SG 值 = 它的所有后继局面的 SG 值中，没出现的最小非负整数（mex）；SG 值非 0 即必胜态。多个独立子游戏，总 SG = 各子游戏 SG 的异或。

入门路径：先背 Nim 的异或结论并会证明（为什么异或为 0 是必败态），再学 SG 定义，最后做"取石子"变体题练习。

📝 算法流程

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;
}

⚠️ 常见坑点

📚 相关题目