sg[i]为0表示i节点先手必败。
首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。
例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Grundy函数g如下：g(x)=mex{ g(y) | y是x的后继 },这里的g（x）即sg[x]
例如：取石子问题，有1堆n个的石子，每次只能取{1，3,4}个石子，先取完石子者胜利，那么各个数的SG值为多少？
sg[0]=0，f[]={1,3,4},
x=1时，可以取走1-f{1}个石子，剩余{0}个，mex{sg[0]}={0}，故sg[1]=1;
x=2时，可以取走2-f{1}个石子，剩余{1}个，mex{sg[1]}={1}，故sg[2]=0；
x=3时，可以取走3-f{1,3}个石子，剩余{2,0}个，mex{sg[2],sg[0]}={0,0}，故sg[3]=1;
x=4时，可以取走4-f{1,3,4}个石子，剩余{3,1,0}个，mex{sg[3],sg[1],sg[0]}={1,1,0},故sg[4]=2;
x=5时，可以取走5-f{1,3,4}个石子，剩余{4,2,1}个，mex{sg[4],sg[2],sg[1]}={2,0,1},故sg[5]=3；
以此类推.....
x 0 1 2 3 4 5 6 7 8....
sg[x] 0 1 0 1 2 3 2 0 1....
计算从1-n范围内的sg值，
s[]存储可以走的步数，s[0]表示可以有多少种走法
s[]需要从小到大排序
1.可选步数为1~m的连续整数，直接取模即可，sg[x] = x % (m+1);
2.可选步数为任意步，sg[x] = x;
3.可选步数为一系列不连续的数，用sg函数计算
模板1（dfs）：
/*
s数组表示合法移动集合，从小到大排序。sNum合法移动个数
sg数组初始化为-1，对每个集合s仅需初始化1次
*/
const int MAXN = ;//s集合大小
const int MAXM = + ;//
int s[MAXN], sNum;
int sg[MAXM]; int dfsSg(int x)
{
if (sg[x] != -) {
return sg[x];
}
int i;
bool vis[MAXN];//sg值小于等于合法移动个数sNum memset(vis, false, sizeof(vis));
for (i = ; i < sNum && s[i] <= x; ++i) {
dfsSg(x - s[i]);
vis[sg[x - s[i]]] = true;
}
for (i = ; i <= sNum; ++i) {
if (!vis[i]) {
sg[x] = i;
break;
}
}
return sg[x];
}
模板2（打表）：
求出所有sg值，有时没必要，用dfs就行
/*
s数组表示合法移动集合，从小到大排序。sNum合法移动个数
sg值对每个集合s仅需求一次
*/
const int MAXN = ;//s集合大小
const int MAXM = + ;//
int s[MAXN], sNum;
int sg[MAXM];
bool exist[MAXN];//sg值小于等于合法移动个数sNum void getSg(int n)
{
int i, j;
sg[] = ;//必败态
for (i = ; i <= n; ++i) {
memset(exist, false, sizeof(exist));
for (j = ; j < sNum && s[j] <= i; ++j) {
exist[sg[i - s[j]]] = true;
}
for (j = ; j <= sNum; ++j) {
if (!exist[j]) {
sg[i] = j;
break;
}
}
}
}
hdu 1848 Fibonacci again and again（sg）
取石子问题，一共有3堆石子，每次只能取斐波那契数个石子，先取完石子者胜利，问先手胜还是后手胜
#include <bits/stdc++.h>
using namespace std; /*
s数组表示合法移动集合，从小到大排序。sNum合法移动个数
sg数组初始化为-1，对每个集合s仅需初始化1次
*/
const int MAXN = ;//s集合大小
const int MAXM = + ;//
int s[MAXN], sNum;
int sg[MAXM]; int dfsSg(int x)
{
if (sg[x] != -) {
return sg[x];
}
int i;
bool vis[MAXN];//sg值小于等于合法移动个数sNum memset(vis, false, sizeof(vis));
for (i = ; i < sNum && s[i] <= x; ++i) {
dfsSg(x - s[i]);
vis[sg[x - s[i]]] = true;
}
for (i = ; i <= sNum; ++i) {
if (!vis[i]) {
sg[x] = i;
break;
}
}
return sg[x];
} int main()
{
int i;
s[] = ;
s[] = ;
for (i = ; i < MAXN; ++i) {
s[i] = s[i - ] + s[i - ];
//printf("%d %d\n", i, s[i]);
}
sNum = ;
int m, n, p;
int sum;
memset(sg, -, sizeof(sg));
while (~scanf("%d%d%d", &m, &n, &p)) {
if (m == && n == && p == ) {
break;
}
dfsSg(m);
dfsSg(n);
dfsSg(p);
sum = sg[m] ^ sg[n] ^ sg[p];
if (sum != ) {
printf("Fibo\n");
} else {
printf("Nacci\n");
}
}
return ;
}
#include <bits/stdc++.h>
using namespace std; /*
s数组表示合法移动集合，从小到大排序。sNum合法移动个数
sg值对每个集合s仅需求一次
*/
const int MAXN = ;//s集合大小
const int MAXM = + ;//
int s[MAXN], sNum;
int sg[MAXM];
bool exist[MAXN];//sg值小于等于合法移动个数sNum void getSg(int n)
{
int i, j;
sg[] = ;//必败态
for (i = ; i <= n; ++i) {
memset(exist, false, sizeof(exist));
for (j = ; j < sNum && s[j] <= i; ++j) {
exist[sg[i - s[j]]] = true;
}
for (j = ; j <= sNum; ++j) {
if (!exist[j]) {
sg[i] = j;
break;
}
}
}
} int main()
{
int i;
s[] = ;
s[] = ;
for (i = ; i < MAXN; ++i) {
s[i] = s[i - ] + s[i - ];
//printf("%d %d\n", i, s[i]);
}
sNum = ;
int m, n, p;
int sum;
getSg();
while (~scanf("%d%d%d", &m, &n, &p)) {
if (m == && n == && p == ) {
break;
}
sum = sg[m] ^ sg[n] ^ sg[p];
if (sum != ) {
printf("Fibo\n");
} else {
printf("Nacci\n");
}
}
return ;
}