st_nec's Blog

第一次写sg函数的题，看起来并不容易的样子= =

直觉看起来，像是sg[x]==0的话，此时先手必败的说= =

显然看不懂证明，也不要在意细节啦。

坑就坑在这一行：if((sg[n]^sg[m]^sg[p])==0)

原来异或时候要打上括号= =，害的我WA了好多次。。

代码：

#include<cstdio>
#include<cstring>
using namespace std;

int f[100],sg[1010],a[1010];

int main(){
	f[1]=1;
	f[2]=2;
	for(int i=3;f[i-1]<=1000;i++){
		f[i]=f[i-1]+f[i-2];
	}
	sg[0]=0;
	for(int i=1;i<=1001;i++){
		sg[i]=i;
		memset(a,0,sizeof(a));
		for(int j=1;f[j]<=i;j++){
			a[sg[i-f[j]]]=1;
		}
		for(int j=0;j<=1001;j++){
			if(a[j]==0){
				sg[i]=j;
				break;
			}
		}
	}
	int n,m,p;
	while(scanf("%d%d%d",&n,&m,&p),(n!=0||m!=0||p!=0)){
		if((sg[n]^sg[m]^sg[p])==0){
			printf("Nacci\n");
		}else{
			printf("Fibo\n");
		}
	}
	return 0;
}