Problem Description：
Alice 和 Bob 在玩一个游戏。给定 k 个数字 a1,a2,……，ak。一开始，有n堆硬币，每堆各有 Xi 枚硬币。Alice 和 Bob 轮流选出一堆硬币，从中取出一些硬币。每次所选硬币的枚数一定要在 a1,a2,……，ak 当中。Alice先取，取光硬币的一方获胜。当双方都采取最优策略时，谁会获胜？题目保证a1,a2……中一定有1.
1<=n<=1000000
1<=k<=100
1<=Xi,ai<=10000
Input：
n=3
k=3
a={1,3,4}
x={5 ,6,7}
Output：
Alice
这和4.1.1中介绍的硬币问题类似，但那道题中只有一堆硬币，而本题中有n堆。如果依然用动态规划算法的话，状态数将高达O（X1*X2*……*Xn）。
为了更高效地求解这个问题，要了解一下Grundy值这一重要概念。利用它，不光是这个游戏，其他许多游戏都可以转换成前面所介绍的Nim。
让我们再来考虑一下只有一堆硬币的情况。硬币枚数所对应的Grundy值的计算方法如下。
int grundy(int x){
S={};
for(i=,……,k){
if(a_i<=x)
//将Grundy（x-a_i）加到S中
}
return //最小的不属于S的非负整数
}
也就是说，当前状态的Grundy值就是除任意一步所能转移到的状态的Grundy值以外的最小非负整数。这样的Grundy值，和Nim中的一个石子堆类似，有如下性质。
Nim中有x颗石子的石子堆，能够转移成0，1，……，x-1颗石子的石子堆；
从Grundy值为x的状态出发，可以转移到Grundy值为0,1，……，x-1的状态；
只不过，与Nim不同的是转移后的Grundy值也有可能增加。不过，对手总能选取合适的策略再转移回相同Grundy值的状态，所以对胜负没有影响。（但是，对于状态可能有循环时，需要注意不分胜负·达成平局（游戏不会结束）的情况。因为在这个游戏中，石子数始终是减少的，所以不会发生平局）
另外，上面的程序是用单纯的递归函数实现的，改成动态规划或记忆化搜索之后，就能够保证求解的复杂度为O（xk）。
了解了一堆硬币的Grundy值的计算方法之后，就可以将它看作Nim中的一个石子堆。Nim中为什么用如下方法判断胜负。
所有石子堆的石子数Xi的XOR
X1 XOR X2 XOR …… XOR Xk
为零则必败，否则必胜
Grundy值等价于Nim中的石子数，所以对于Grundy值的情况，有
所有硬币堆的Grundy值的XOR
grundy(X1) XOR grundy(X2) XOR ……XOR grundy(Xk)
为零则必败，否则必胜
不光是这个游戏，在许多游戏中，都可以根据“当前状态的Grundy值等于除任意一步所能转移到的状态的Grundy值以外的最小非负整数”这一性质，来计算Grundy值，再根据XOR来判断胜负。
//输入
int N,K,X[MAX_N],A[MAX_K];
//利用动态规划计算Grundy值的数组
int grundy[MAX_N+];
void solve(){
//轮到自己时剩0枚则必败
grundy[]=;
//计算grundy值
int max_x= *max_element(X,X+N);
for(int j=;j<max_x;j++){
set<int> s;
for(int i=;i<K;i++)
if(A[i]<=j)
s.insert(grundy[j-A[i]]);
int g=;
while(s.count(g)!=) g++;
grund[j]=g;
}
//判断胜负
int x=;
for(int i=;i<N;i++)
x^=grundy[x[i]];
if(x) puts("Alice");
else puts("Bob");
}
SG函数：
首先引入mex函数，mex(x)=未在集合S中出现，且不超过x的最小非负整数。
举个例子：
S={1,2,3}，mex(4)=0;
S={0,1,2,3},mex(4)=4;
S={0,1,3},mex(4)=2;
这个看起来和推理毫不相关……好啦，开始回忆下推理过程吧！
我们在推理博弈时，引入了“必胜局势”和“必败局势”，并且我们发现：“必胜局势”可以转化为“必胜局势”或“必败局势，而”必败局势“只能转化为”必胜局势“。这意味着，谁拿到了”必败局势“，只能把”必胜局势“留给对方，那就只能乖乖走进对方布下的圈套，不断陷入”必败局势“喽！
再引入SG定理和SG函数，SG(x)=mex(SG(所有通过x能达到的”局势“))，那么对于n堆石子的取石子游戏，若SG(1)^SG(2)^……^SG(n)==0，则先手必败，否则先手必胜。（^为异或，即在二进制中，异或双方相同位取0，不同位取1.）
那么在实际做题时，就可以直接预处理出所有SG值，求结果时直接异或即可。
以这题为例，若每次最少取1，最多取3，那么：
SG(0)=0;
SG(1)=1，因为1可以取到0，而SG(0)=0，所以把0去掉后，未出现过的最小非负整数为1；
SG(2)=2，同理，2可以取到1或0，排除掉SG(0)和SG(1)，未出现过的最小非负整数为2；
SG(3)=3；
SG(4)=0，因为4可以取到1,2,3，但不能取到0（最多取3个嘛！），所以虽然排除1,2,3，未排除0，最小非负整数为0；
SG(5)=1；
……以此类推；
因为只有一堆石子，不用异或，直接判断SG(x)是否等于0即可判断x是否为”必胜局势“
模板：
//f[]：可以取走的石子个数
//sg[]:0~n的SG函数值
//hash[]:mex{}
int f[N],sg[N],hash[N];
void getSG(int n)
{
int i,j;
memset(sg,,sizeof(sg));
for(i=;i<=n;i++)
{
memset(hash,,sizeof(hash));
for(j=;f[j]<=i;j++)
hash[sg[i-f[j]]]=;
for(j=;j<=n;j++) //求mes{}中未出现的最小的非负整数
{
if(hash[j]==)
{
sg[i]=j;
break;
}
}
}
}