hdu_1848_Fibonacci again and again(博弈sg函数)

 1 #include<cstdio>
 2 #define F(i,a,b) for(int i=a;i<=b;i++)
 3 /*
 4 计算从0-N范围内的SG值。
 5 s(存储可以走的步数，s[0]表示可以有多少种走法)
 6 s[]需要从小到大排序
 7 1.可选步数为1~m的连续整数,直接取模即可,SG(x)=x%(m+1);
 8 2.可选步数为任意步，SG(x) = x;
 9 3.可选步数为一系列不连续的数，用GetSG()计算
10 */
11 const int N=1001;
12 int sg[N];bool hash[N];
13 void get_sg(int *s,int N){
14     F(i,0,N)sg[i]=0;
15     F(i,1,N){
16         F(j,0,N)hash[j]=0;
17         for(int j=1;s[j]<=i&&j<=s[0];j++)hash[sg[i-s[j]]]=1;
18         F(j,0,N)if(!hash[j]){sg[i]=j;break;}
19     }
20 }
21 int f[20],n,m,p;
22 int main(){
23     f[1]=1,f[2]=2,f[0]=16;
24     F(i,3,16)f[i]=f[i-1]+f[i-2];
25     get_sg(f,1000);
26     while(~scanf("%d%d%d",&m,&n,&p),m+n+p){
27         if(sg[m]^sg[n]^sg[p])puts("Fibo");
28         else puts("Nacci");
29     }
30     return 0;
31 }