HDU 1848 Fibonacci again and again【SG函数】

对于Nim博弈，任何奇异局势（a，b，c）都有a^b^c=0。

延伸：任何奇异局势(a1, a2,… an)都满足 a1^a2^…^an=0

首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。

例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Garundy函数g如下：

　　　　　　g(x)=mex{ g(y) | y是x的后继 }。

SG函数性质：

1，所有的终结点SG值为0（因为它的后继集合是空集）

2，SG为0的顶点，它的所有后继y都满足SG不为0

3，对于一个SG不为0的顶点，必定存在一个后继满足SG为0

4，满足组合游戏性质：所有SG为0定点对应P点，SG大于0顶点对应N点

SG定理（Sprague-Grundy Theorem）：

　　 g(G)=g(G1)^g(G2)^…^g(Gn)。游戏的和的SG函数值是它的所有子游戏的SG函数值的异或。

#include<stdio.h>

#include<string.h>

const int N=;

int p[N],sg[N],f[];

void init(){

    int i,j;

    f[]=,f[]=;

    for(i=;;i++){

        f[i]=f[i-]+f[i-];

        if(f[i]>N)    break;

    }

    for(i=;i<=;i++){

        for(j=;f[j]<=i;j++){

            p[sg[i-f[j]]]=i;

        }

        for(j=;j<=i;j++){

            if(p[j]!=i){

                sg[i]=j;

                break;

            }

        }

    }

}

int main(){

    init();

    int n,m,p;

    while(~scanf("%d%d%d",&n,&m,&p)){

        if(!n&&!m&&!p)    break;

        if(sg[n]^sg[m]^sg[p])    puts("Fibo");

        else                    puts("Nacci");

    }

    return ;

}

巴特西

HDU 1848 Fibonacci again and again【SG函数】

最新文章

热门文章