博弈论进阶\(——\)\(Multi\)-\(SG\)

博弈\(——\)命运让你们相遇，可若是差了那么一点缘分，注定不会有结局，这种结局，从一开始就注定了。

\(SG\)函数拓展\(——\)\(Multi\)-\(SG\)

感谢贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》一文

一、定义

在以往的\(SG\)当中，我们的操作是取若干颗石子，那么在\(Multi\)-\(SG\)游戏当中就多了这样一种操作——将一堆石子分成若干堆。

定义：

• \(Multi\)-\(SG\)游戏规定，在符合拓扑原则的前提下，一个单一游戏的后继可以为多个单一游戏。
• 其他规则与\(SG\)游戏相同

二、\(Multi\)-\(Nim\)

和之前的定义相同，下面这个问题就是将\(Nim\)游戏变形为\(Multi\)-\(Nim\)。
题意大致为:
给定\(n\)堆石子，两人轮流操作，每次选一堆石子，取任意石子或则将石子分成两个更小的堆\((\)非\(0)\)，取得最后一个石子的为胜。
Nim or not Nim?

对于这个问题，很显然我们可以用\(SG\)函数以及\(SG\)定理解决它，也就是第一种操作直接预处理，第二种操作令\(SG[x] = SG[i]\oplus SG[x-j](i\)是小于\(x\)的数字\()\)。
不幸的是这个题目的范围太大了，直接这样是过不了的。
所以，我们可能需要找规律。

先写一个打表程序：

void init(){
    sg[0] = 0,sg[1] = 1;
    for(ll i = 2;i <= 505;i++){
        memset(vis,false,sizeof vis);
        for(ll j = 1;j <= i;j++) vis[sg[i-j]] = true;
        for(ll j = 1;j < i;j++) vis[sg[j]^sg[i-j]] = true;
        ll j = 0;
        while(vis[j])sg[i] = ++j;
    }
}

再看一看成果（截图就不发了）：
sg[1] = 1 sg[2] = 2 sg[3] = 4 sg[4] = 3
sg[5] = 5 sg[6] = 6 sg[7] = 8 sg[8] = 7
sg[9] = 9 sg[10] = 10 sg[11] = 12 sg[12] = 11
sg[13] = 13 sg[14] = 14 sg[15] = 16 sg[16] = 15

我们发现这是有规律的，即

\(SG(x)=\left\{\begin{matrix}x-1，x\mod4 = 0 \\x，x\mod4=1~or~2 \\ x+1，x\mod4=3 \end{matrix}\right.\)

现在我们就可以运用这个规律直接求出每一个数的\(SG\)值，再把整个问题看作\(n\)个有向图游戏，使用\(SG\)定理。

int main(){
    ios::sync_with_stdio(false);
    ll t;cin>>t;
    while(t--){
        ll n;cin>>n;
        ll sg = 0;
        for(ll i = 1;i <= n;i++){
            ll x;cin>>x;
            if(x%4 == 0) sg^=x-1;
            else if(x%4 == 3) sg^= x+1;
            else sg ^= x;
        }
        if(sg) cout<<"Alice"<<endl;
        else cout<<"Bob"<<endl;
    }
    return 0;
}

3、\(Multi - SG\)游戏

处理过简单的\(Nim\)问题之后，我们再回来看看这给我们解决\(Multi\)-\(SG\)问题有了什么启示。
是的，\(Multi - SG\)游戏的处理异常简单，因为实际上它与正常的\(SG\)游戏相比，只是在于多了一种后继状态，而这一种后继状态又可以利用\(SG\)定理求异或和算出\(SG\)值。

当然这里并没有给出严格的证明，为什么可以这样做（当然是因为我证不出来）。