欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

<模板>计算SG函数-(hdu 1848 Fibonacci again and again)

程序员文章站 2022-04-01 12:41:34
...

题目传送门


Solution

关于什么是SG函数和SG定理

和普通的Nim游戏不同的是,Nim可以选任意的石子拿走,因此Nim游戏中每一堆石子的SG函数为这一堆中石子的数量
而这道题并不能任意拿,只能按斐波那契数列的个数取,所有此时SG函数的值需要从所有子集取mex操作得到。
计算SG函数的模板如下

    f[0]=1;f[1]=1;
    for(int i=2;i<=20;++i) f[i]=f[i-1]+f[i-2];
    sg[0]=0;s[0]=1;
    for(int i=1;i<=M;++i){
        memset(s,0,sizeof(s));
        for(int j=0;j<=20&&f[j]<=i;++j)
            s[sg[i-f[j]]]=1;//判断是否出现
        for(int j=0;j<=M;++j)
            if(!s[j]){
                sg[i]=j;//mex操作
                break;
            }
    }

Code

// by spli
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

const int M=1010;
int n,m,p;
int f[100];
int sg[M],s[M];

void pre(){
    f[0]=1;f[1]=1;
    for(int i=2;i<=20;++i) f[i]=f[i-1]+f[i-2];
    sg[0]=0;s[0]=1;
    for(int i=1;i<=M;++i){
        memset(s,0,sizeof(s));
        for(int j=0;j<=20&&f[j]<=i;++j)
            s[sg[i-f[j]]]=1;
        for(int j=0;j<=M;++j)
            if(!s[j]){
                sg[i]=j;
                break;
            }
    }
}

int main(){
    pre();
    while(scanf("%d%d%d",&n,&m,&p)&&(n+m+p)){
        if(sg[n]^sg[m]^sg[p]) puts("Fibo");
        else puts("Nacci");
    }
    return 0;
}