分类： 博弈论

图文无关，因为空和白玩的游戏中没有一个是ICG类的。

NIM游戏是一类经典的博弈论题目。
众所周知，NIM游戏的结果就是把所有的答案异或起来即可。为什么可以这么做呢？
我们定义，对于一个「均衡组合博弈（ICG）」 ，我们定义两种局面状态：P（先手必败）和N（先手必胜）。
首先我们可以知道，在ICG中，博弈是一定会终止的；同时，终止局面是P局面。如果说一个局面的所有子局面都是N局面或者P局面，那么这个局面也一定是N局面或者P局面：这是因为N局面和P局面存在性质：
一个局面是P局面，当且仅当它的所有子局面都是N局面；一个局面是N局面，当且仅当它的所有子局面中存在一个是P局面。
这也就意味着，对于任何一种状态，我们都可以判定它是N状态还是P状态。
那么，初始状态的N-P性是可以判断的。
如何计算一个局面的N-P性呢？
我们定义一种运算，使得：
P局面经过这种运算只能变成N局面；
N局面经过这种运算可以变成P局面。
当我们用一个数列描述一个局面后，我们惊讶地发现：异或——这里指的是将局面中的每一个子部分异或起来——是满足这个性质的。
我们定义，异或值为零的局面是必败局面；异或值非0的局面是必胜局面。
我们将描述这个局面的数列异或起来，如果它等于零，那么任意一种「减少」操作——导致它的一个值减少的，一定会导向一种P局面；
而对于一种P局面，依据按位异或的特性，一定可以通过减少最大的数，来变更想变更的任意一位。
故而，我们发现，对于任意一种局面，我们可以用异或运算来判断它的N-P性。
事实上，两者之间并不存在那么直接的数学上的对应关系。可以将NIM游戏理解为一个数学模型。
这是一种指代关系。换句话说，为了更方便地处理它，
我们可以将这个局面转化为数学模型，而异或运算刚好满足其性质——这并不是说异或运算本身就是这个局面的变化。
当理解这一点之后，异或的意义就很显然了。

#include<iostream>
#include<cstdio>
using namespace std;
int n,a[10005];
void init(){
    scanf("%d",&n);
    int x=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        x^=a[i];
    }
    if(x){
        puts("Yes");
    }else{
        puts("No");
    }
    return;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

这是一道基础的复杂博弈论题——我到现在都不是很能理解。
其实我也不太懂SG函数，我就口chao胡xi一下这题的做法吧。
对于\(x,y st: x<y\)，我们定义对于x,y的SG函数SG(S)，其中S是一个局面。 我们定义关于一个局面S的后继S’，使得S’可以从S转移得到。 所以我们定义一个集合T，包含了局面S的所有后继的SG值。 对于必败局面，我们令它的SG值为0，否则为1。 则\(SG(S)=mex(T)\)，其中mex表示最小的不在集合中的非负整数。 所以， $$SG(x,y)=mex(SG(x,y-x),SG(x,y-2*x),$$

$$SG(x,y-3*x)…SG(x,y%x))$$ 我们又知道，对于其中的每一个SG函数，递推式都是成立的。 所以事实上，当\(x/y>1时，SG(x,y)=1\)，这是因为当\(x/y==1\)始终是等于\(!(SG(y%x,x))\)
所以事实上\(SG(x,y)\)只取决于\(SG(x,y%x)\)的值。

#include<iostream>
#include<cstdio>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int a,b;

inline bool SG(int x,int y){
    if(!x){
        return 0;
    }
    if(y/x==1){
        return !SG(y%x,x);
    }else{
        return 1;
    }
}
void init(){
    scanf("%d%d",&a,&b);
    bool bo=SG(Min(a,b),Max(a,b));
    if(bo){
        puts("Stan wins");
    }else{
        puts("Ollie wins");
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}