HDU1848 (Fibonacci again and again)[公平组合博弈，SG函数]

发表于 | 更新于 | | 阅读次数：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1848

尼姆游戏变型，每次每堆石子只能取走斐波那契数个石子。
打一个SG表，SG值为0的为P局势，SG值为1的为N局势。判断三堆石子的SG值异或和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
#include <cstring>
using namespace std;
int fibo[17];
int sg[1009];
bool vis[17];
const int maxn=1000;
int main() {
    fibo[0]=1;fibo[1]=1;
    for(int i=2;i<=16;i++) fibo[i]=fibo[i-1]+fibo[i-2];
    sg[0]=0;
    for(int i=1;i<=maxn;i++) {
        for(int j=0;j<=16;j++) vis[j]=0;
        for(int j=1;j<=16 && i-fibo[j]>=0;j++) vis[sg[i-fibo[j]]]=1;
        for(int j=0;;j++) if(!vis[j]) {
            sg[i]=j;
            break;
        }
    }
    int a,b,c,sg1,sg2,sg3;
    while(~scanf("%d%d%d",&a,&b,&c)) {
        if(a==0 && b==0 && c==0) break;
        sg1=sg[a];
        sg2=sg[b];
        sg3=sg[c];
        if(sg1^sg2^sg3) puts("Fibo");
        else puts("Nacci");
    }
}