HDOJ 1848 Fibonacci again and again

题目链接：HDOJ1848

题目的状态转移给定是Fibonnacci的前几个数，需要提前打表计算

然后求SG（x），只需要去计算SG（x-1），SG（x-2）……SG（x-Fk），其中Fk是min【x，题中可能的最大Fibonacci】

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int N=1050;
int sg[N];
int f[N];

int g(int x){
	int mex[1010];
	memset(mex,0,sizeof(mex));
	if (sg[x]!=-1) return sg[x];
	for(int i=1;f[i]<=x;i++)
		mex[sg[x-f[i]]]=1;
	for(int i=0;;i++)
		if (!mex[i]) return sg[x]=i;
}

int main(){
	//freopen("input.txt","r",stdin);
	memset(sg,-1,sizeof(sg));
	int i,m,n,p;
	f[0]=f[1]=1;
	for(i=2;i<=16;i++) f[i]=f[i-1]+f[i-2];
	for(int i=0;i<1001;i++) g(i);
    while(scanf("%d%d%d",&m,&n,&p)!=EOF){
        if(!m&&!n&&!p) break;
        if((sg[m]^sg[n]^sg[p])==0)
            printf("Nacci\n");
        else
            printf("Fibo\n");
    }
	return 0;
}