SG函数是博弈论中的一个重要技巧，其直接含义为 当前节点到距其最近的“必败点”的距离 ，在面对多次博弈叠加的问题时，可以更加高效地用于计算当前节点为必败点还是必胜点。

以Problem – 1848为例：

AC代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int h1, h2, h3, fi[1002], sg[1002], v[1002];
void getsg(int x)
{
    for (int i = 0; i <= x; ++i) // 求i张牌对应的sg值
    {
        memset(v, 0, sizeof(v));
        for (int j = 1; fi[j] <= i; ++j) // 取fi[j]张牌
            v[sg[i - fi[j]]] = 1;
        for(int j = 0;;++j)
            if (!v[j])
            {
                sg[i] = j;
                break;
            }
    }
}
int main()
{
    fi[0] = fi[1] = 1;
    for (int i = 2; i <= 16; i++)
        fi[i] = fi[i - 1] + fi[i - 2];
    memset(sg, -1, sizeof(sg));
    getsg(1000);
    while (cin >> h1 >> h2 >> h3 && (h1 || h2 || h3))
    {
        if (!(sg[h1] ^ sg[h2] ^ sg[h3])) cout << "Nacci" << endl;
        else cout << "Fibo" << endl;
    }
    return 0;
}

SG函数计算过程：

假如计算SG[i]，则需要遍历“当我有i张牌时，所有可以取牌的方式”，假设取牌数为x，然后将所有可能的SG[i – x]的值排除，最后从0开始遍历，第一个遇到的未被排除的值即为当前所求的SG[i]。

多博弈叠加时求初始状态为必胜点还是必败点：

假设有三堆牌，分别包含a,b,c张牌，则只需求三者对应的SG值的异或结果即可，即若SG[a]^SG[b]^SG[c] = 0，则初始状态为必败点，否则为必胜点。