一瞻颂、 ICG
ICG（Impartial Combinatorial Games），即公平的組合游戲郑象，其定義如下：
- 兩名選手贡这。
- 兩名選手輪流行動(dòng)，每一次行動(dòng)可以在有限合法操作集合中選擇一個(gè)厂榛。
- 游戲的任何一種可能的局面(position)盖矫，合法操作集合只取決于這個(gè)局面本身；局面的改變稱為“移動(dòng)”(move)击奶。
- 若輪到某位選手時(shí)辈双，該選手的合法操作集合為空，則這名選手判負(fù)柜砾。
在ICG游戲中湃望，先手不是必勝就是必?cái) ＷC明過(guò)程：
雙方互相決策痰驱，有限步驟证芭，可以用樹(shù)來(lái)描述，樹(shù)的每個(gè)葉子節(jié)點(diǎn)表示對(duì)先手而言是必勝或者必?cái) ?/p>
則對(duì)于樹(shù)上的每個(gè)節(jié)點(diǎn)：
- 當(dāng)這個(gè)節(jié)點(diǎn)輪到先手行動(dòng)時(shí)担映，若其存在子節(jié)點(diǎn)對(duì)先手而言必勝废士，則當(dāng)前節(jié)點(diǎn)對(duì)先手而言必勝，否則當(dāng)前節(jié)點(diǎn)對(duì)先手而言必?cái) ?/li>
- 當(dāng)這個(gè)節(jié)點(diǎn)輪到后手行動(dòng)時(shí)蝇完，若其存在子節(jié)點(diǎn)對(duì)先手而言必?cái)」傧酰瑒t當(dāng)前節(jié)點(diǎn)對(duì)先手而言必?cái)〈Ｈ铮駝t當(dāng)前節(jié)點(diǎn)對(duì)先手而言必勝。
按照上述過(guò)程氢架，可以從決策樹(shù)的葉子節(jié)點(diǎn)開(kāi)始向根節(jié)點(diǎn)向上推出決策樹(shù)上每個(gè)節(jié)點(diǎn)對(duì)于先手而言必勝還是必?cái)∩悼В氏仁植皇潜貏倬褪潜財(cái) ?/p>
二、 Nim游戲
Nim游戲是ICG的一種达箍，通常的Nim游戲的定義是這樣的：有若干堆石子没龙，每堆石子的數(shù)量都是有限的，合法的移動(dòng)是“選擇一堆石子并拿走若干顆（不能不拿）”缎玫，如果輪到某個(gè)人時(shí)所有的石子堆都已經(jīng)被拿空了硬纤，則判負(fù)（因?yàn)樗丝虥](méi)有任何合法的移動(dòng)）。
三赃磨、 Bouton定理
假設(shè)Nim游戲的石子有堆筝家，第
堆的石子個(gè)數(shù)我們用
表示，則我們可以使用
表示一個(gè)Nim游戲的局面邻辉。對(duì)于
的Nim游戲局面溪王，當(dāng)且僅當(dāng)
時(shí)（其中
是按位異或運(yùn)算），先手必勝值骇。
證明：
- 對(duì)于
的Nim游戲局面
莹菱，我們?cè)O(shè)
。則必存在
吱瘩，其二進(jìn)制表示在
的最高位上為1（異或運(yùn)算的性質(zhì)）道伟，且有
。則對(duì)于當(dāng)前局面下的先手可以通過(guò)合法的移動(dòng)將第
堆石子取到只剩
個(gè)使碾，那么此時(shí)游戲局面變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=(a_1%2C%20a_2%2C%20...%2C%20a_%7Bi-1%7D%2C%20a_i%20%5Cwedge%20k%2C%20a_%7Bi%2B1%7D%2C%20...%2C%20a_n)" alt="(a_1, a_2, ..., a_{i-1}, a_i \wedge k, a_{i+1}, ..., a_n)" mathimg="1">蜜徽，而
。用一句話來(lái)講票摇，就是異或和不為0的局面一定存在合法移動(dòng)可以變?yōu)楫惢蚝蜑?的局面拘鞋。
- 對(duì)于
的Nim游戲局面
個(gè)矢门，則有
盆色，則必有
（可用反證法證明）。用一句話來(lái)講祟剔，就是異或和為0的局面無(wú)論怎樣合法地進(jìn)行移動(dòng)傅事，都將轉(zhuǎn)變?yōu)楫惢蚝筒粸?的局面。
- 對(duì)于局面
峡扩，其異或和為0，對(duì)于先手而言是必輸?shù)木置妗?/li>
- 對(duì)于任何異或和不為0的局面障本，先手只需要按照策略將其轉(zhuǎn)變?yōu)楫惢蚝蜑?的局面教届，就能保證后手永遠(yuǎn)只能拿到異或和為0的局面响鹃。又因?yàn)槊恳淮魏戏ǖ囊苿?dòng)都將導(dǎo)致石子個(gè)數(shù)減少，故總的移動(dòng)步數(shù)是有限的案训，最終后手將拿到
四轩触、 SG函數(shù)
通過(guò)SG函數(shù)，每個(gè)ICG都可以轉(zhuǎn)換成Nim游戲家夺。
SG函數(shù)的定義域?yàn)镮CG的決策樹(shù)上的所有節(jié)點(diǎn)脱柱，其具體定義為：，其中
（minimal excludant）是施加于集合的運(yùn)算拉馋，表示最小的不屬于這個(gè)集合的非負(fù)整數(shù)榨为，比如
，
煌茴，
随闺。
對(duì)于ICG的決策樹(shù)上的節(jié)點(diǎn)，我們可以把它想象成一個(gè)只有一堆石子蔓腐，個(gè)數(shù)為
的Nim游戲矩乐。
對(duì)于節(jié)點(diǎn)的子節(jié)點(diǎn)
：
- 根據(jù)SG函數(shù)的定義，必有
合住。
- 若
绰精，則根據(jù)SG函數(shù)的定義，
節(jié)點(diǎn)必定存在子節(jié)點(diǎn)
使得
透葛。倘若先手嘗試使得局面的SG函數(shù)值變大笨使，由局面
移動(dòng)到局面
的情況萨蚕。
- 對(duì)于全體
上的所有整數(shù)。我們從局面
的石子上取走若干石子奕翔，使剩下一堆個(gè)數(shù)為
的石子。
當(dāng)ICG中存在個(gè)互相不干擾的移動(dòng)類型時(shí)浩蓉，我們可以將這
種移動(dòng)類型視為
堆石子派继，將該ICG視為
堆石子的Nim游戲宾袜。運(yùn)用前面的Bouton定理，該ICG的先手必勝與否的情況可以通過(guò)計(jì)算每個(gè)移動(dòng)類型下的初始狀態(tài)的SG函數(shù)驾窟，并計(jì)算這些SG函數(shù)值的異或和來(lái)得出庆猫。
五、例題HDU 1848 Fibonacci again and again
HDU 1848 Fibonacci again and again：
這題就是個(gè)ICG绅络，其中在三堆石子上取石子的操作可以分成3種互相不干擾的移動(dòng)類型月培，故可將該問(wèn)題轉(zhuǎn)換為3堆石子的Nim游戲。這三堆石子的初始狀態(tài)為恩急、
杉畜、
，計(jì)算
假栓，若該值不為0則先手必勝寻行，輸出“Fibo”，否則先手必?cái)∝揖＃敵觥癗acci”拌蜘。
參考AC代碼：
#include <bits/stdc++.h>
using namespace std;
int f[500] = {1, 2}, mex[1001];
bool used[1001][1001];
int calc_mex(int x) {
if (mex[x] >= 0) return mex[x];
if (!x) return mex[x] = 0;
for (int i=0; f[i]<=x; i++) used[x][calc_mex(x-f[i])] = 1;
for (int i=0;;i++)
if (!used[x][i]) return mex[x] = i;
}
int main() {
for (int i=2;;i++) {
f[i] = f[i-1] + f[i-2];
if (f[i] > 1000) break;
}
memset(mex, -1, sizeof(mex));
int m, n, p;
while (scanf("%d %d %d", &m, &n, &p) && (m || n || p)) {
int ans = calc_mex(m) ^ calc_mex(n) ^ calc_mex(p);
printf(ans ? "Fibo\n" : "Nacci\n");
}
return 0;
}
