经典NIM游戏的一个简单变形，游戏中有N堆石子，每次走步可以选择：
- 取走某堆的任意个石子(不可不取);
- 将石子拆分成三堆(三堆都不可为空);
同样先计算每个石堆(子游戏)的SG值，然后求异或和。
一个游戏状态的拆分实际上等价于划分成三个子游戏，这也是这个游戏状态的后继状态，SG值即是三个子游戏SG值的异或和，枚举这些拆分即可。由于游戏状态的转移有方向性，所以不需要DFS求解，直接按照状态从小到大递推即可。
打表后发现SG(N)存在规律：
- SG(N) = N-1(N%8==0)
- SG(N) = N+1(N%8==7)
- 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)
