sg函数模板：
实现的环节：
1、递推式求出全部位置的sg值；
2、sq[n]=mex{sq[y],y属于n通过一次变化达到的值}
3、求( sq[n] )一组数中未出现的最小非负整数，通过将一组原本为false的数组（flag），把出现的数对应数组的位置的值改为true，
再做一次无限循环，直到遇到未曾改的数组元素，终止循环，并得到sq[ n ]的值为该位置的大小值；
再次嘱咐：
1、环节2中sq[0]=0,即环节1实现递推的循环从i=1开始；
2、牢记环节3所用到的flag数组的集体赋值（这里使用memset（flag，0，sizeof(flag) ) )必须在实现递推的每次循环都要执行一次，
因为每一次不同的循环（即不同的i）对应有不同的y，进而有不同的sq[y],所以需要全为0的flag数组（不然flag会受上次循环的影响）
才能得到这次出现的数，才能准确实现环节3；
模板：
/* n 表示所有中石头最多的那堆石头数； m 表示取石头的操作总数； S[]表示该操作取石头的个数； */ int sq[n+1]; void sg(int n) { sq[0]=0; int flag[n+1]; for(int i=1;i<=n;++i) { memset(flag,0,sizeof(flag)); for(int j=0;j<m;j++) if(i-S[j]>=0)flag[sq[i-S[j]]]=1; for(int j=0; ;j++) if(!flag[j]){sq[i]=j;break；} } }模板应用：
HDU 1848
/* hdu 1848 解决代码 S_num 表示取石头的操作总数； 函数 f( n ),quire_S(),是本题的预处理（需要自己设计斐波拉契函数求出S[]和S_num； */ #include<iostream> #include<string.h> using namespace std; int S[1000]; int sq[1001]; int S_num; int f(int n) { if(n==1) return S[1]; if(n==2) return S[2]; return S[n]=f(n-1)+f(n-2); } void quire_S(int stones) { for(int i=1; ;++i) { if(f(i)>1000){ S_num=i-1;break;} } } void sg(int n) { sq[0]=0; int flag[1001]; for(int i=1;i<=n;i++) { memset(flag,0,sizeof(flag)); for(int j=1;j<=S_num;j++) { if(i-S[j]>=0)flag[sq[i-S[j]]]=1; } for(int j=0; ;j++) if(!flag[j]){sq[i]=j;break;} } } int main () { S[1]=1; S[2]=2; quire_S(1000); sg(1000); int m,n,p; while(cin>>m>>n>>p&&m&&n&&p) { if(sq[m]^sq[n]^sq[p])cout<<"Fibo"<<endl; else cout<<"Nacci"<<endl; } return 0; }