Sprague-Geundy函数(SG函数)

必胜点与必败点：
p：必败点，即谁在这个点，只要双方正确操作，在这个点的一方必输。
N：必胜点，即谁在这个点，只要双方正确操作，在这个点的一方必胜。
一般博弈题可以通过画PN图找规律来解题。
例题：http://acm.hdu.edu.cn/showproblem.php?pid=1847

从图中可以看出规律，只要牌的数量是3的倍数Kiki必输。
代码戳我可看
再来看说明是sg函数：
这里引入一个集合mex{x}表示不属于这个集合的最小整数。
**小性质：**如果mex的集合都大于零，那么最小的一定为零，如果有一个数等于零，那么最小的一定大于零。
对于任意状态sg(x) = mex{s},s表示x的后继状态sg函数值的集合。
当且仅当sg(x) = 0时，x为必败点。
取石子问题
假设有1堆n个石子，每次可以取{1，3，4}个石子，求sg值：
假设有x个石子
sg(0) = 0.
x=1 可以取走{1}个石子，剩余{0}个石子sg(1) = mex(sg(0)) = 1,
x=2 可以取走{1}个石子，剩余{1}个石子sg(2) = mex(sg(1)) = mex(mex(sg(0))) = 0,
x=3 可以取走{1，3}个石子，剩余{2，0}个石子，sg(3)=mex(sg(2),sg(0)) = 1
…

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

**分析：**这道题给你的是每个堆的石子的数量，并且限制了每次只能取斐波那契数的石子数量，所有可以用sg函数来求解。
求sg：

int sg[1005],fib[20],vis[1005],h[1005];
void get_sg(int n)
{
   
    for(int i = 1; i <= n; i++){
   
        memset(vis,0,sizeof(vis));
        for(int j = 0; fib[j] <= i; j++){
   
            vis[sg[i - fib[j]]] = 1;
        }
        for(int j = 0; j <= n; j++){
   
            if(!vis[j]){
   
                sg[i] = j;
                break;
            }
        }
    }
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <time.h>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const ll ds = 1e15+7;
const double p = 3.141592653589793238462643383;
using namespace std;

//srand(time(NULL));
// m = rand() % 10 + 1;
// cout << m;

int sg[1005],fib[20],vis[1005],h[1005];
void get_sg(int n)
{
   
    for(int i = 1; i <= n; i++){
   
        memset(vis,0,sizeof(vis));
        for(int j = 0; fib[j] <= i; j++){
   
            vis[sg[i - fib[j]]] = 1;
        }
        for(int j = 0; j <= n; j++){
   
            if(!vis[j]){
   
                sg[i] = j;
                break;
            }
        }
    }
}

int main(){
   
    fib[0] = 1;
    fib[1] = 1;
    for(int i = 2; i <= 16; i++) fib[i] = fib[i - 1] + fib[i - 2];
    int n,m,p;
    get_sg(1005);
    while(~scanf("%d%d%d",&n,&m,&p)){
   
        if(n == 0 || m == 0 || p == 0) break;
        if(sg[n] ^ sg[m] ^ sg[p]) printf("Fibo\n");
        else printf("Nacci\n");
    }
    return 0;
}

参考大牛博客：https://blog.csdn.net/luomingjun12315/article/details/45555495