hdu1848 sg打表

 果然是神器。

#include<stdio.h>
#include<string.h>
#define maxn 1002
int f[30],sg[maxn],hash[maxn];
void getsg(int len)
{
    int i,j;
    memset(sg,0,sizeof(sg));
    for(i=1;i<=1000;i++)
    {
        memset(hash,0,sizeof(hash));
        for(j=0;f[j]<=i&&j<len;j++)
        {
            hash[sg[i-f[j]]]=1;
        }
        for(j=0;j<=1000;j++)
        {
            if(!hash[j])
            {
                sg[i]=j;
                break;
            }
        }
    }
}
int main()
{
    int i,j,n,m,p;
    f[0]=1;
    f[1]=2;
    for(i=2;;i++)
    {
        if(f[i-1]+f[i-2]>1000)
            break;
        f[i]=f[i-1]+f[i-2];
    }

    getsg(i);

    /*for(i=0;i<=1000;i++)
    {
        printf("%d ",sg[i]);
        if(i%10==0)printf("
");
    }
    puts("");*/
    
    while(scanf("%d%d%d",&n,&m,&p)!=EOF)
    {
        if(!n&&!m&&!p)break;
        if((sg[n]^sg[m]^sg[p])==0)
        {
            printf("Nacci
");
        }
        else printf("Fibo
");
    }
}