HDU 1848 Fibonacci again and again

Description

三堆石子，任取F[i]（斐波那契数）个，取光为胜

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

Analyze

游戏和的SG函数等于各个游戏SG函数的Nim和

SG函数

首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

对于任意状态 x ， 定义 SG(x) = mex(S), 其中 S 是 x 后继状态的SG函数值的集合。

如 x 有三个后继状态分别为 SG(a),SG(b),SG(c)，那么SG(x) = mex{SG(a),SG(b),SG(c)}。

这样集合S的终态必然是空集，所以SG函数的终态为 SG(x) = 0,当且仅当 x 为必败点P时。

步骤：

1、使用 数组f 将 可改变当前状态 的方式记录下来。

2、然后我们使用 另一个数组 将当前状态x 的后继状态标记。

3、最后模拟mex运算，也就是我们在标记值中 搜索 未被标记值 的最小值，将其赋值给SG(x)。

4、我们不断的重复 2 - 3 的步骤，就完成了 计算1~n 的函数值。

原文出处： https://www.cnblogs.com/ECJTUACM-873284962/p/6921829.html

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;///改变当前状态的方案数
const int MAXN = 10010;///石子数(状态数,对应打表上限n)

int f[25];         ///1.预处理：可改变当前状态的方案数
int SG[MAXN];     ///0 ~ n 的SG函数值（n是打表上限）
bool st[MAXN];     /// i 后继状态的集合

void getSG(int n)
{
    memset(SG, 0, sizeof(SG));
    ///SG[0] = 0;
    for(int i = 1; i <= n; ++i)///当前石子数
    {
        memset(st, 0, sizeof(st));

        ///2.枚举f[N]中每种方案并标记
        for(int j = 0; f[j] <= i && j <= N; ++j)
            st[ SG[ i - f[j] ] ] = 1;


        ///3.模拟mex运算(最小的不属于集合st的非负整数)
        for(int j = 0; ; ++j)
            if(!st[j])
            {
                SG[i] = j;
                break;
            }
    }
}

int main()
{
    f[0] = f[1] = 1;
    for(int i = 2; i <= 22; ++i)
        f[i] = f[i - 1] + f[i - 2];
    getSG(1000);

    int a, b, c;
    while(~scanf("%d%d%d", &a, &b, &c))
    {
        if(a == 0 && b == 0 && c == 0)
            break;
        if(SG[a] ^ SG[b] ^ SG[c])
            cout << "Fibo" << '\n';
        else
            cout << "Nacci" << '\n';
    }
    return 0;
}

各量对应清楚，易写混，易RE

还有 == 优先级高于 ^(位运算的优先级仅优于赋值运算符、逗号运算符)