HDU-5795 NIM游戏简单变形 [2016多校]

经典NIM游戏的一个简单变形，游戏中有N堆石子，每次走步可以选择：

1. 取走某堆的任意个石子(不可不取);
2. 将石子拆分成三堆(三堆都不可为空);

同样先计算每个石堆(子游戏)的SG值，然后求异或和。
一个游戏状态的拆分实际上等价于划分成三个子游戏，这也是这个游戏状态的后继状态，SG值即是三个子游戏SG值的异或和，枚举这些拆分即可。由于游戏状态的转移有方向性，所以不需要DFS求解，直接按照状态从小到大递推即可。

打表后发现SG(N)存在规律：

1. SG(N) = N-1(N%8==0)
2. SG(N) = N+1(N%8==7)
3. SG(N) = N(其他)

#include <iostream>
using namespace std;
#define MAX_MEX 5050

int mex[MAX_MEX];
void calc_sg(int n){
    sg[0] = 0;
    for (int i=1;i<=n;i++){
        memset(mex,0,sizeof(mex));
        for (int j=0;j<i;j++) mex[sg[j]] = 1;
        for (int x=1;x<i;x++){
            for (int y=1;y<i;y++){
                if (i-x-y>0){
                    int z = i-x-y;
                    int xor_sum = sg[x]^sg[y]^sg[z];
                    mex[xor_sum] = 1;
                }
            }
        }
        for (int j=0;;j++){
            if (!mex[j]) {
                sg[i] = j;
                break;
            }
        }
    }
}

int main(){
    int t;
    cin>>t;
    while(t--){
        int n,ans=0,si;
        cin>>n;
        for (int i=0;i<n;i++) {
            cin>>si;
            if (si%8==0) ans ^= (si-1);
            else if (si%8==7) ans ^= (si+1);
            else ans ^= si;
        }
        if (ans) cout<<"First player wins."<<endl;
        else cout<<"Second player wins."<<endl;
    }
    return 0;
}

两篇关于NIM游戏模型的文章

(http://sighingnow.github.io/algorithm/game_theory_sg_function.html)
(https://maxmute.com/2016/01/07/%E6%B5%85%E6%9E%90sg%E5%87%BD%E6%95%B0%E4%B8%8Esg%E5%AE%9A%E7%90%86.html)