模板 - 数学 - 博弈论 - SG函数

f[i]表示状态i的后继状态，把它的后继状态push_back()进去，然后调用getSG()就可以得到SG函数。无法转移的状态都是失败状态，这种写法貌似只能向标号更小的状态转移（本身这个图就是DAG，就有拓扑序，所以本质上无所谓，更何况取石子非常直观），所以一般f[0]就是失败状态。当然也可能会有别的失败状态。

多个公平组合游戏的和，只需要把他们分别的SG函数求出来然后求个异或和即可。

vector<int> f[1005];

int SG[1005], S[1005];
int getSG() {
    for(int i = 0; i <= n; ++i)
        SG[i] = 0;
    for(int i = 1; i <= n; i++) {
        int l = f[i].size();
        for(int j = 0; j <= l; j++)
            S[j] = 0;
        for(auto &j : f[i])
            S[SG[j]] = 1;
        for(int j = 0; j <= l; j++) {
            if(!S[j]) {
                SG[i] = j;
                break;
            }
        }
    }
    return SG[n];
}

模板 - 数学 - 博弈论 - SG函数

原文：https://www.cnblogs.com/KisekiPurin2019/p/12297664.html