SG博弈函数模板

下面这两个模版应该就比较严密了，这个里边的f[]是从零开始的。

转载出处：转自：http://blog.csdn.net/primoblog/article/details/13376057

1、sg打表

 1 //f[]：可以取走的石子个数  
 2 //sg[]:0~n的SG函数值  
 3 //hash[]:mex{}  
 4 int f[K],sg[N],hash[N];  
 5 void getSG(int n)  
 6 {  
 7         memset(sg,0,sizeof(sg));  
 8         for(int i=1; i<=n; i++) {  
 9                 memset(hash,0,sizeof(hash));  
10                 for(int j=0; f[j]<=i && j < k; j++) //k是f[]的有效长度  
11                         hash[sg[i-f[j]]]=1;  
12                 for(int j=0; ; j++) {   //求mes{}中未出现的最小的非负整数  
13                         if(hash[j]==0) {  
14                                 sg[i]=j;  
15                                 break;  
16                         }  
17                 }  
18         }  
19 }

2dfs

    //注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍    
    //n是集合s的大小 S[i]是定义的特殊取法规则的数组    
    int s[N],sg[N],n;    
    int getSG(int x)    
    {    
            if(sg[x]!=-1)    
                    return sg[x];    
            bool vis[M];    
            memset(vis,0,sizeof(vis));    
            for(int i=0; i<n; i++) {    
                    if(x>=s[i])    
                            vis[getSG(x-s[i])]=1;    
            }    
            for(i=0;; i++)    
                    if(!vis[i]) {    
                            sg[x]=i;    
                            break;    
                    }    
            return sg[x];    
    }