SG函数

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N = 100;
 4 int step[N];//可以走的步数
 5 int SG[N];
 6 bool hash[N];
 7 void getSG(int n, int len)//step的长度
 8 {
 9     int i,j;
10     SG[0] = 0;
11     for(i=1; i<=n; ++i)
12     {
13         memset(hash,0,sizeof(hash));
14         for(j=0;j<len; ++j)
15             if(i-step[j]>=0)
16                 hash[SG[i-step[j]]] = true;
17         for(j=0; j<=n; ++j)
18             if(!hash[j])
19                 break;
20         SG[i] = j;
21     }
22 }
23 int len,n;//len为step的长度
24 int dfs_sg(int x)//获得sg[x]
25 {
26     int i;
27     if(SG[x]!=-1)
28         return SG[x];
29     bool vis[N];
30     for(i=0; i<len; ++i)
31         if(x-step[i]>=0)
32         {
33             dfs_sg(x-step[i]);
34             vis[SG[x-step[i]]] = true;
35         }
36     for(i=0;i<=n; ++i)
37         if(!vis[i])
38             break;
39     return SG[x] = i;    
40 }
41 int main()
42 {
43 
44     return 0;
45 }