SG函数

 1 //f[N]:可改变当前状态的方式，N为方式的种类，f[N]要在getSG之前先预处理
 2 //SG[]:0~n的SG函数值
 3 //S[]:为x后继状态的集合
 4 int f[N],SG[MAXN],S[MAXN];
 5 void  getSG(int n){
 6     int i,j;
 7     memset(SG,0,sizeof(SG));
 8     //因为SG[0]始终等于0，所以i从1开始
 9     for(i = 1; i <= n; i++){
10         //每一次都要将上一状态 的 后继集合 重置
11         memset(S,0,sizeof(S));
12         for(j = 0; f[j] <= i && j <= N; j++)
13             S[SG[i-f[j]]] = 1;  //将后继状态的SG函数值进行标记
14         for(j = 0;; j++) if(!S[j]){   //查询当前后继状态SG值中最小的非零值
15             SG[i] = j;
16             break;
17         }
18     }
19 }