SG函数（回合制游戏）
首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
对于任意状态 x ， 定义 SG(x) = mex(F)，其中F 是 x 后继状态的SG函数值的集合。最后返回值（也就是SG(X)）为0为必败点，不为零必胜点。
如x有三个后继状态分别为SG（a），SG（b），SG（c），那么SG（x）= mex{SG(a)，SG(b)，SG(c)}。经过一系列运算后，集合S的终态必然为空集，所以SG函数的终态为SG（x）= 0，当且仅当x为必败点。
假如说是在一个游戏中有多个石子堆该怎么办了。我们只需要把对每个石子堆进行sg函数的调用，将得到的所有的值进行异或。得出来的结果为0则该情形为必败态。否则为必胜态。
————————————————
取石子问题
有1堆n个石子，每次只取{1，3，4}个石子，先取完石子者胜利，那么各个数的SG值为多少？
SG（0）= 0，每次能取走石子个数集合f = {1，3，4}，剩余石子的个数就是当前x的后继状态（）
x=1 时，可以取走1 - f{1}个石子，剩余{0}个，所以 SG[1] = mex{ SG[0] }= mex{0} = 1;
x=2 时，可以取走2 - f{1}个石子，剩余{1}个，所以 SG[2] = mex{ SG[1] }= mex{1} = 0;
x=3 时，可以取走3 - f{1,3}个石子，剩余{2,0}个，所以 SG[3] = mex{SG[2],SG[0]} = mex{0,0} =1;
x=4 时，可以取走4- f{1,3,4}个石子，剩余{3,1,0}个，所以 SG[4] = mex{SG[3],SG[1],SG[0]} = mex{1,1,0} = 2;
x=5 时，可以取走5 - f{1,3,4}个石子，剩余{4,2,1}个，所以SG[5] = mex{SG[4],SG[2],SG[1]} =mex{2,0,1} = 3;
以此类推…
x 0 1 2 3 4 5 6 7 8…
SG[x] 0 1 0 1 2 3 2 0 1…
由上述实例我们就可以得到SG函数值求解步骤，那么计算1~n的SG函数值步骤如下：
1、使用 数组f 将 可改变当前状态 的方式记录下来。
2、然后我们使用 另一个数组 将当前状态x 的后继状态标记。
3、最后模拟mex运算，也就是我们在标记值中 搜索 未被标记值 的最小值，将其赋值给SG(x)。
4、我们不断的重复 2 - 3 的步骤，就完成了 计算1~n 的函数值。
Java模板：
1 //arr[]：可以取走的石子个数
2 //sg[]：0~n的SG函数值
3 //hash[]：mex{}
4 static int MAXN = 1000;
5 static int N = 10;
6 static int[] sg = new int[MAXN];
7 static int[] arr = new int[N];
8 static boolean[] hash = new boolean[MAXN];
9 static boolean[] visited = new boolean[MAXN];
10
11 //打表法求sg函数值
12 private static void getSG(int n){
13 Arrays.fill(sg,0);
14 for(int i=1;i<=n;i++){
15 Arrays.fill(hash,false);
16 //注意这里j从0开始
17 for(int j=0;arr[j]<=i;j++){
18 hash[ sg[ i-arr[j] ] ] = true;//SG(x) = mex(F),F是x的后继状态的SG函数值的集合。为true的都是后继状态。
19 }
20 for(int j=0;j<=n;j++){
21 if(!hash[j]){
22 sg[i] = j;//模拟mex运算，取最小的不属于这个集合的非负整数
23 break;
24 }
25 }
26 }
27 }
28
29 //dfs方式求解x的sg函数值
30 private static int mex(int x){
31 if(sg[x] != -1) return sg[x];
32
33 for(int i=0;i<=10;i++){
34 int temp = x - arr[i];
35 if(temp < 0) break;
36 sg[temp] = mex(temp);
37 visited[sg[temp]] = true;
38 }
39 for(int i=0;;i++){
40 if(!visited[i]){
41 sg[x] = i;
42 break;
43 }
44 }
45 return sg[x];
46 }
47
48 //此函数是对<题目给出的每次能取到的石子数>进行初始化
49 private static void f(){
50 arr[0] = 1;
51 for(int i=1;i<=10;i++){
52 arr[i] = arr[i-1]*2;
53 }
54 }
具体情况，具体分析！