用于把多堆问题简化成每个单堆问题的异或和
Sprague-Grundy定理（SG定理）：
游戏和的SG函数等于各个游戏SG函数的Nim和。这样就可以将每一个子游戏分而治之，从而简化了问题。
SG函数：
首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
对于任意状态 x ， 定义 SG(x) = mex(S),其中 S 是 x 后继状态的SG函数值的集合。如 x 有三个后继状态分别为 SG(a),SG(b),SG(c)，那么SG(x) = mex{SG(a),SG(b),SG(c)}。 这样 集合S 的终态必然是空集，所以SG函数的终态为 SG(x) = 0,当且仅当 x 为必败点P时。
即，该状态的SG值 = mex{ 后继状态的SG值 }
http://acm.hdu.edu.cn/showproblem.php?pid=3980
用SG数组记录每个状态的SG值，f数组用来进行mex{}的计算
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<vector>
#include<iostream>
#define MAXN 1000005
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
int SG[1005],f[1005];
int getsg(int n,int m)
{
SG[0]=0;
for(int i=1;i<=n;i++)//从1开始，逆推出n的SG值
{ SG[i]=0;
if(i<m) continue;
memset(f,0,sizeof(f));
for(int j=m;j<=i;j++)//枚举后继状态
{
f[SG[j-m]^SG[i-j]]=1;
}
for(int k=0;;k++)//mex计算
{
if(!f[k])
{
SG[i]=k;
break;
}
}
}
return SG[n];
}
int main()
{ int T,d=1;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
if(n<m) {
printf("Case #%d: abcdxyzk
",d++);
continue;
}
n-=m;
int x=getsg(n,m);
if(x) printf("Case #%d: abcdxyzk
",d++);
else printf("Case #%d: aekdycoin
",d++);
}
return 0;
}