博弈论——sg，mex
sg性质：1.在末态的状态点为N态。
2.P态的下一步有一个是N态
3.N态的下一步全部是P态。
当然这是对于单点一个游戏的情形，也相当于NIM只有一堆石子。
mex(minimal excludant)，很俗地可以解释为：mex{S}表示S集合中从0开始，最小未出现的数字。
关于sg与mex的关系，可以引用这里http://www.cnblogs.com/Knuth/archive/2009/09/05/1561007.html的一段话：
对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Garundy函数g如下：g(x)=mex{ g(y) | y是x的后继 }。
来看一下SG函数的性质。首先，所有的terminal position所对应的顶点，也就是没有出边的顶点，其SG值为0，因为它的后继集合是空集。然后对于一个g(x)=0的顶点x，它的所有后继y都满足g(y)!=0。对于一个g(x)!=0的顶点，必定存在一个后继y满足g(y)=0。
以上这三句话表明，顶点x所代表的postion是P-position当且仅当g(x)=0（跟P-positioin/N-position的定义的那三句话是完全对应的）。
关于sg叠加的效果，很神奇发现它们满足sg(G) = sg(G1)^sg(G2)^……^sg(Gn)。对于与博弈有关的核心就是这些了。多刷刷题，自然心里就明了了。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int sg[][];
int stamp[*]={},stamps=;
int sgx(int r,int c){
stamps++;
for(int i=;i<=r-i;i++) // 1 c（只有一行）【r-1 c】 不能被继续，故需要从2开始。
stamp[sg[i][c]^sg[r-i][c]] = stamps;
for(int i=;i<=c-i;i++)
stamp[sg[r][i]^sg[r][c-i]] = stamps;
for(int i=;;i++)
if(stamp[i] < stamps)
{
sg[r][c] = i;
break;
}
return sg[r][c];
}
int main()
{
for(int i=;i<;i++)
sg[][i] = sg[i][] = ; for(int i=;i<;i++)
for(int j=i;j<;j++)
sg[i][j] = sg[j][i] = sgx(i,j);
int n,m;
while(scanf("%d%d",&n,&m) != EOF){
if(sg[n][m]) printf("WIN\n");
else printf("LOSE\n");
}
return ;
}