SG函数

打表法：

对于数据小又容易超时的题，可以采取打表法。

打表法就是将所有输入情况的答案保存在代码中，输入数据后直接输出就是可以了。

打表法具有快速，易行（可以写暴力枚举程序）的特点。缺点就是代码可能太大了，或者情况覆盖不完，对于一般不会超时，数据规模适合打表，为了简洁也可以打表。

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     }

具体情况，具体分析！