Fibonacci again and again

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4248 Accepted Submission(s): 1768

Problem Description 任何一個大學生對菲波那契數列(Fibonacci numbers)應該都不會陌生，它是這樣定義的：
F(1)=1;
F(2)=2;
F(n)=F(n-1)+F(n-2)(n>=3);
所以，1,2,3,5,8,13……就是菲波那契數列。
在HDOJ上有不少相關的題目，比如1005 Fibonacci again就是曾經的浙江省賽題。
今天，又一個關於Fibonacci的題目出現了，它是一個小游戲，定義如下：
1、 這是一個二人游戲;
2、 一共有3堆石子，數量分別是m, n, p個；
3、 兩人輪流走;
4、 每走一步可以選擇任意一堆石子，然後取走f個；
5、 f只能是菲波那契數列中的元素（即每次只能取1，2，3，5，8…等數量）；
6、 最先取光所有石子的人為勝者；

假設雙方都使用最優策略，請判斷先手的人會贏還是後手的人會贏。
Input 輸入數據包含多個測試用例，每個測試用例占一行，包含3個整數m,n,p（1<=m,n,p<=1000）。
m=n=p=0則表示輸入結束。
Output 如果先手的人能贏，請輸出“Fibo”，否則請輸出“Nacci”，每個實例的輸出占一行。
Sample Input

1 1 1
1 4 1
0 0 0

Sample Output

Fibo
Nacci

Author lcy Source ACM Short Term Exam_2007/12/13 題目：http://acm.hdu.edu.cn/showproblem.php?pid=1848
用SG函數做的第一道題。 對於SG函數，還是有些不太懂， 但是，我看下面說的，就有些明白了：

首先定義mex(minimal excludant)運算，這是施加於一個集合的運算，表示最小的不屬於這個集合的非負整數。

例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

對於一個給定的有向無環圖，定義關於圖的每個頂點的Sprague-Grundy函數g如下：g(x)=mex{ g(y) | y是x的後繼 },這裡的g（x）即sg[x]

例如：取石子問題，有1堆n個的石子，每次只能取{1，3,4}個石子，先取完石子者勝利，那麼各個數的SG值為多少？

sg[0]=0，f[]={1,3,4},

x=1時，可以取走1-f{1}個石子，剩余{0}個，mex{sg[0]}={0}，故sg[1]=1;

x=2時，可以取走2-f{1}個石子，剩余{1}個，mex{sg[1]}={1}，故sg[2]=0；

x=3時，可以取走3-f{1,3}個石子，剩余{2,0}個，mex{sg[2],sg[0]}={0,0}，故sg[3]=1;

x=4時，可以取走4-f{1,3,4}個石子，剩余{3,1,0}個，mex{sg[3],sg[1],sg[0]}={1,1,0},故sg[4]=2;

x=5時，可以取走5-f{1,3,4}個石子，剩余{4,2,1}個，mex{sg[4],sg[2],sg[1]}={2,0,1},故sg[5]=3；

以此類推.....

x 0 1 2 3 4 5 6 7 8....

sg[x] 0 1 0 1 2 3 2 0 1...

計算從1-n范圍內的SG值。

f(存儲可以走的步數，f[0]表示可以有多少種走法)

f[]需要從小到大排序

1.可選步數為1~m的連續整數，直接取模即可，SG(x) = x % (m+1);

2.可選步數為任意步，SG(x) = x;

3.可選步數為一系列不連續的數，用GetSG()計算

上述是自jumping_frog博文的建立SG模板時的解釋，稍後我也會做個SG函數的模板。

這道題，有了上述方法，就簡單了。 首先建立f數組，就是Fibonacci數列。 然後預處理求1000以內的SG數組，通過模板：

// 獲得SG數組函數模板，t代表f數組的個數，n代表要求的sg數組上限
// f數組就是能取的個數（對於此題就是Fibonacci數列
// 有時，對於t已知就不需要單獨傳參
void get_sg(int t,int n)
{
    int i,j;
    memset(sg,0,sizeof(sg));
    for(i=1;i<=n;i++)
    {
        memset(mex,0,sizeof(mex));
        // 對於屬於g(x)後繼的數置1
        for( j=1 ;j<=t && fib[j]<=i ;j++ )
            mex[sg[i-fib[j]]]=1;
        // 找到最小不屬於該集合的數
        for( j=0 ; j<=n ; j++ )
            if(!mex[j])
                break;
        sg[i] = j;
    }
}

SG的題，很多都可以看成是多個Nim博弈。 然後就可以分析奇異態，非奇異態來確定答案了。 關於，Nim博弈可見博客：http://blog.csdn.net/lttree/article/details/24874819
然後就是此題完整代碼：

/************************************************
*************************************************
*        Author:Tree                            *
*From :http://blog.csdn.net/lttree              *
* Title : Fibonacci again and again             *
*Source: hdu 1848                               *
* Hint  : SG                                    *
*************************************************
*************************************************/
#include 
#include 
int fib[21];    //fib保存Fibonacci數列
int sg[1001];//sg[]來保存SG值
bool mex[1001];//mex{}
// 構建SG數組，函數各步驟意義詳見上面模板
void get_sg(int n)
{
    int i,j;
    memset(sg,0,sizeof(sg));
    for(i=1;i<=n;i++)
    {
        memset(mex,0,sizeof(mex));
        for( j=1 ;fib[j]<=i ;j++ )
            mex[sg[i-fib[j]]]=1;

        for( j=0 ; j<=n ; j++ )
            if(!mex[j])
                break;
        sg[i] = j;
    }
}
int main()
{
    int i,m,n,p;
    // 構建Fibonacci數列
    fib[0]=1,fib[1]=1;
    for(i=2;i<21;++i)   fib[i]=fib[i-1]+fib[i-2];
    // 預處理獲得sg數組
    get_sg(1000);
    while( scanf("%d%d%d",&m,&n,&p) && m+n+p )
    {
        if( (sg[m]^sg[n]^sg[p])==0 )  printf("Nacci\n");
        else    printf("Fibo\n");
    }
    return 0;
}