问题背景:
有n堆石子,给定取子规则,最终第一个无法取石子的人输,即轮到他时,每一堆石子都为0
NIM游戏的合并而已
当且仅当各个石子堆石子数目SG值异或结果为0时,先手的人必败,反之必胜
即res = sg(a1)^sg(a2)^···sg(an) = 0时,先手必败
具体求SG函数代码如下
int sg(int p)
{
int t;
bool g[101] = {0};
for(int i=1;i<=k;i++)
{
t = x - a[i];
//a[i]数组存储取子规则
if(t<0) continue;
if(f[t]==-1)
{
f[t] = sg(t);
}
g[f[t]] = 1;
}
for(int i=0;;i++)
{
if(!g[i]) return i;
}
}