<模板>计算SG函数-(hdu 1848 Fibonacci again and again)
程序员文章站
2022-04-01 12:41:34
...
Solution
和普通的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;
}