SG函数_牛客博客

SG函数

对于任意状态 x ，定义 SG(x) = mex(S),其中 S 是 x 后继状态的 SG 函数值的集合。如 x 有三个后继状态分别为 SG(a),SG(b),SG(c)，那么 SG(x)=mex{SG(a),SG(b),SG(c)}。这样集合 S 的终态必然是空集，所以SG函数的终态为 SG(x)=0，当且仅当 x 为必败点P时。
注:
mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
SG 定理：游戏和的SG函数等于各个游戏SG函数的Nim和。
Nim和：各个数相异或的结果

//f[N]:可改变当前状态的方式，N为方式的种类，f[N]要在getSG之前先预处理
//SG[]:0~n的SG函数值
//S[]:为x后继状态的集合
int f[N],SG[MAXN],S[MAXN];
void  getSG(int n){
    int i,j;
    memset(SG,0,sizeof(SG));
    //因为SG[0]始终等于0，所以i从1开始
    for(i = 1; i <= n; i++){
        //每一次都要将上一状态 的 后继集合 重置
        memset(S,0,sizeof(S));
        for(j = 0; f[j] <= i && j <= N; j++)
            S[SG[i-f[j]]] = 1;  //将后继状态的SG函数值进行标记
        for(j = 0;; j++) if(!S[j]){   //查询当前后继状态SG值中最小的非零值
            SG[i] = j;
            break;
        }
    }
}

尼姆博弈（Nimm Game）：

尼姆博弈指的是这样一个博弈游戏：有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。
结论：把每堆物品数全部异或起来，如果得到的值为0，那么先手必败，否则先手必胜。
SG定理：
若 $图片说明$ ，先手必胜。
若 $图片说明$ ，先手必败。

新玩法

取到最后一件物品的人失败。
结论：当每堆石子数量都不超过 1 时，n 为奇数先手必败。剩下的就和尼姆博奕的结论一致。
可以把一堆石子分成不相等的两堆，不能操作为败

void getSG(int n) {
//    memset(sg, 0, sizeof(sg));
    for(int i = 1; i <= n; ++ i) {
        memset(s, 0, sizeof(s));                            //S[]:为x后继状态的集合
        for(int j = 1; j*2 < i; ++ j) s[sg[j]^sg[i-j]] = 1; // sg定理
        while(s[sg[i]]) ++sg[i];                            // mex(...)
    }
}

尼姆博奕先手必胜，第一步有几种走法。
结论：把一堆石头移出游戏，去掉一部分再加入游戏，看此时 sg 是否能为零，即 (ans^a[i]) < a[i]。

    long long ans = 0;
    for(int i = 1; i <= n; ++ i) {
        scanf("%lld", &a[i]);
        ans ^= a[i];
    }
    int res = 0;
    for(int i = 1; i <= n; ++ i) {
        if ((ans^a[i]) < a[i]) res ++;
    }

巴什博弈

只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取 1 个，最多取 m 个，最后取光者得胜。
结论：若 n % (m+1) == 0，则先手必败，否则先手必胜

高级玩法

取石子的数量，不是 1~m 内的连续数字，而是只能在数组 a 中选。
方法一：定义 P 为先手必败，N 为先手必胜，P 的后继全是 N，N 的后继包含 P，依次类推寻找周期即可。
方法二：sg函数打表。

void getSG(int n, int t[], int m) { // 石块数量，拿去规则
//    memset(sg, 0, sizeof(sg));
    for(int i = 1; i <= n; ++ i) {
        memset(s, 0, sizeof(s));                                      //S[]:为x后继状态的集合
        for(int j = 1; t[j] <= i && j <= m; ++ j) s[sg[i-t[j]]] = 1;  //将后继状态的SG函数值进行标记
        while(s[sg[i]]) ++sg[i];                           // mex(...)
    }
}

威佐夫博奕（Wythoff's game）

有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。
结论：若 a == int((b-a)*1.618)，则先手必败，否则先手必胜。

斐波那契数列

只有一堆n个物品，两个人轮流从这堆物品中取物，规则是先手不能在第一次把所有的石子取完，之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。约定取走最后一个石子的人为赢家。
结论：若 n 为斐波那契数，先手必败，否则先手必胜。