HDU 1848 Fibonacci again and again【SG函数】

时间:2021-11-13 14:02:10

对于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 ;
}