SG函数

在讲解SG函数之前先了解一下必胜点和必败点，也就是所谓的必胜态和必败态。

P点（必败点）：当你处于这个情况的时候，无论进行怎样的操作，对方都能取胜。

N点（必胜点）：当你处于这个情况的时候，你能进行恰当的操作，保证一定能取胜。

必胜点和必败点的性质：

1、所有终结点是必败点P。（一般都是以此为基本前提进行推理，换句话说，我们以此为假设）。

2、从任何必胜点N操作，至少有一种方式可以进入必败点P。

3、无论如何操作，必败点P都只能进入必胜点N。

算法介绍

SG函数

在讲解SG函数之前先介绍mex运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如$mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0$。

对于任意状态 x ， 定义$SG(x) = mex(S)$，其中 S 是 x 后继状态的SG函数值的集合。如 x 有三个后继状态分别为$SG(a),SG(b),SG(c)$，那么$SG(x) = mex{SG(a),SG(b),SG(c)}$。 这样集合S的终态必然是空集，所以SG函数的终态为$SG(x) = 0$,当且仅当 x 为必败点P时。

这个SG(x)就是SG函数，用这个SG函数，我们能够将很多问题简化。

不是很理解的话来个例子就懂了。

【实例】取石子问题

有1堆n个的石子，每次只能取1, 3, 4个石子，先取完石子者胜利，那么各个数的SG值为多少？

SG[0]=0，f[]={1,3,4},

x=1 时，可以取走1 - f{1}个石子，剩余{0}个，所以 SG[1] = mex{ SG[0] }= mex{0} = 1;

x=2 时，可以取走2 - f{1}个石子，剩余{1}个，所以 SG[2] = mex{ SG[1] }= mex{1} = 0;

x=3 时，可以取走3 - f{1,3}个石子，剩余{2,0}个，所以 SG[3] = mex{SG[2],SG[0]} = mex{0,0} =1;

x=4 时，可以取走4- f{1,3,4}个石子，剩余{3,1,0}个，所以 SG[4] = mex{SG[3],SG[1],SG[0]} = mex{1,1,0} = 2;

x=5 时，可以取走5 - f{1,3,4}个石子，剩余{4,2,1}个，所以SG[5] = mex{SG[4],SG[2],SG[1]} =mex{2,0,1} = 3;

以此类推…..

x 0 1 2 3 4 5 6 7 8….

SG[x] 0 1 0 1 2 3 2 0 1….

一般当SG函数值为0表示必败态，非零代表必胜态。（在博弈中不存在不确定态）

由上述实例我们就可以得到SG函数值求解步骤，那么计算1~n的SG函数值步骤如下：

1、使用数组f将可改变当前状态的方式记录下来。

2、然后我们使用另一个数组将当前状态x的后继状态标记。

3、最后模拟mex运算，也就是我们在标记值中搜索未被标记值的最小值，将其赋值给SG(x)。

4、我们不断的重复2 - 3的步骤，就完成了计算1~n的函数值。

SG定理

游戏和的SG函数等于各个游戏SG函数的Nim和。这就是著名的SG定理，通过SG定理我们能够将多个子问题用Nim和连接起来或者将一个问题分成几个子问题来解决。表达形式为$res=SG[1]⊕SG[2]⊕SG[3]⊕…⊕SG[n]$，即每个子问题的SG函数的异或和。对一些经典博弈不是很清楚的请参照这里进行进一步理解。

经典例题

题目大意

给你三堆石子，每堆m,n,p个，两人轮流取石子，每次只能取斐波那契数列中的数，即1,2,3,5,8…等。问先手胜还是后手胜。

解题思路

先预处理出1000以下的所有sg函数值，然后用sg定理得出问题的解。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define endl '\n'
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

set<int> s;
int sg[1010],vis[1010];

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b, ll mod) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans = (ans * a) % mod;
		a = (a * a) % mod, b >>= 1;
	}
	return ans % mod;
}

void SG(int x) {
	rep(i, 1, x) {
		memset(vis, 0, sizeof(vis));
		for (auto x : s) {
			if (x > i)	break;
			vis[sg[i - x]] = 1;
		}
		for (int j = 0;; j++) {
			if (!vis[j]) {
				sg[i] = j; break;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int a = 1, b = 1;
	while (b <= 1000) {
		s.insert(b);
		int t = b;
		b += a, a = t;
	}
	SG(1000);
	int n, m, p; 
	while (cin >> n >> m >> p&&n||m||p) {
		if (sg[n] ^ sg[m] ^ sg[p])	cout << "Fibo" << endl;
		else cout << "Nacci" << endl;
	}
	return 0;
}