(step8.2.6)hdu 1848(Fibonacci again and again——組合博弈)

題目大意:輸入3個整數m,n,p,分別表示3堆石頭中的石頭個數     解題思路:   1)斐波那契數列的第16個數fib[16] == 1597   2)(sg[m]^sg[n]^sg[p])   。一定要加括號，否則會WA     代碼如下：  

/* 
 * 1848_1.cpp 
 * 
 *  Created on: 2013年9月1日 
 *      Author: Administrator 
 */  
  
#include <iostream>  
  
  
using namespace std;  
  
const int maxn = 1001;  
int sg[maxn];  
int f[maxn];  
int hash[maxn];  
  
void getSG(int n){  
  
    int i,j;  
    memset(sg,0,sizeof(sg));  
    for(i = 1 ; i<= n ; ++i){  
        memset(hash,0,sizeof(hash));  
        for(j = 1 ; f[j] <= i ; ++j ){  
            hash[sg[i-f[j]]] = 1;  
        }  
  
        for(j = 0 ; j <= n ; ++j){  
            if(hash[j] == 0){  
                sg[i] = j;  
                break;  
            }  
        }  
    }  
}  
  
int main(){  
    int m,n,p;  
  
    f[0] = 1;  
    f[1] = 1;  
    int i ;  
    for(i = 2 ; i <= 16 ; ++i){//這裡之所以取16是因為fib[16] 已經是 1597,已經大於n的最大值  
        f[i] = f[i - 1] + f[i - 2];  
    }  
    getSG(1000);  
    while(scanf("%d%d%d",&m,&n,&p)!=EOF,m||n||p){  
        if((sg[m]^sg[n]^sg[p]) == 0){//sg[m]^sg[n]^sg[p]外面別忘了加括號(),否則會WA  
            printf("Nacci\n");  
        }else{  
            printf("Fibo\n");  
        }  
    }  
}