博弈论模板问题

1.HDU 1848

任何一个大学生对菲波那契数列(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、 最先取光所有石子的人为胜者； 假设双方都使用最优策略，请判断先手的人会赢还是后手的人会赢。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int f[20], SG[1005], mex[1005];
int getSG(int n) {
    SG[0] = 0;//必败态
    for (int i = 1; i <= n; i ++) {
        memset(mex, 0, sizeof(mex));
        for (int j = 1; f[j] <= i; j ++)
            mex[SG[i - f[j]]] = 1;//对i节点的每个后继进行mex运算，类似于一种标记，1代表出现过 
        for (int j = 0; ; j ++)
            if (!mex[j]) {//j是在i的后继中没有出现最小非负整数 
                SG[i] = j;
                break;
            } 
    }
    return SG[n];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    f[1] = 1, f[2] = 2;
    for (int i = 3; i <= 16; i ++)
        f[i] = f[i - 1] + f[i - 2];
    int n, m, p;
    while (cin >> n >> m >> p) {
        if (n == 0 && m == 0 && p == 0) break;
        if (getSG(n) ^ getSG(m) ^ getSG(p)) cout << "Fibo" << '\n';
        else cout << "Nacci" << '\n';
    }
    return 0;
}