算法学习笔记（博弈论中的SG函数）

定义$SG$函数:

对于状态$x$和它的所有$k$个后继状态$y_1,y_2,...,y_k$：

S G ( x ) = m e x { S G ( y 1 ) , S G ( y 2 ) , . . . , S G ( y k ) } SG(x) = mex\{SG(y_1), SG(y_2), ..., SG(y_k)\} SG(x)=mex{SG(y1​),SG(y2​),...,SG(yk​)}

($mex$函数的值表示不属于集合的最小非负整数)

现在对所有起点的$SG$函数值做异或和，若异或和为$0$，则这个状态为必败状态。若不为$0$，则为必败状态。

现给出证明：

当一个状态没有后继状态时，求$mex$集合为空集合，$SG$函数的值为$0$。即最终态的$SG$函数值必为$0$，而对于一个$SG$函数值不为$0$的状态，在由他的后继状态组成的节点中，肯定会存在一个节点的$SG$函数值为$0$，也就是说，对于一个$SG$函数值不为$0$的状态，总是存在一个操作使它走向一个$SG$函数值为$0$的状态。

而对于一个$SG$函数值为$0$的状态，在由他的后继状态组成的节点中，肯定不存在一个节点的$SG$函数值为$0$。

所以类比$Nim$游戏(算法学习笔记（Nim游戏）)，我们可以得出上述$SG$定理。

$SG$定理适用于任何公平的两人游戏，它常被用于决定游戏的输赢结果。

在使用方面，常常通过记忆化搜索打表，再从表中寻找结果的规律，最后化简$SG$函数的求值方法。

例题：[SDOI2009] E&D

[SDOI2009] E&D

题目描述

小 E 与小 W 进行一项名为 E&D 游戏。

游戏的规则如下：桌子上有 $2n$ 堆石子，编号为 $1\sim 2n$。其中，为了方便起见，我们将第 $2k-1$ 堆与第 $2k$ 堆（$1\le k\le n$）视为同一组。第 $i$ 堆的石子个数用一个正整数 $S_i$ 表示。

一次分割操作指的是，从桌子上任取一堆石子，将其移走。然后分割它同一组的另一堆石子，从中取出若干个石子放在被移走的位置，组成新的一堆。操作完成后，所有堆的石子数必须保证大于 $0$。显然，被分割的一堆的石子数至少要为 $2$。两个人轮流进行分割操作。如果轮到某人进行操作时，所有堆的石子数均为 $1$，则此时没有石子可以操作，判此人输掉比赛。

小 E 进行第一次分割。他想知道，是否存在某种策略使得他一定能战胜小 W。因此，他求助于小 F，也就是你，请你告诉他是否存在必胜策略。例如，假设初始时桌子上有 $4$ 堆石子，数量分别为 $1,2,3,1$。小 E 可以选择移走第 $1$ 堆，然后将第 $2$ 堆分割（只能分出 $1$ 个石子）。接下来，小 W 只能选择移走第 $4$ 堆，然后将第 $3$ 堆分割为 $1$ 和 $2$。最后轮到小 E，他只能移走后两堆中数量为 $1$ 的一堆，将另一堆分割为 $1$ 和 $1$。这样，轮到小 W 时，所有堆的数量均为 $1$，则他输掉了比赛。故小 E 存在必胜策略。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行一个整数 $N$，表示桌子上共有 $N$ 堆石子，这里的 $N$ 即为题目描述中的 $2n$。

第二行 $N$ 个整数 $S_{1\dots N}$。

输出格式

对于每组数据，如果小 E 必胜，则一行一个字符串 YES，否则一行一个字符串 NO。

样例 #1

样例输入 #1

2
4
1 2 3 1
6
1 1 1 1 1 1

样例输出 #1

YES
NO

提示

对于 $20\%$ 的数据，$N=2$。

对于另外 $20\%$ 的数据，$N\le 4$，$S_i\le 50$。

对于 $100\%$ 的数据，$1\le T\le 20$，$1\le N\le 2\times 10^4$ 且 $N$ 为偶数，$1\le S_i\le 2\times 10^9$。

接下来直接给出未降低复杂度的暴力代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 9;

int a[N];

map<pair<int, int>, int> mp;       //做记忆化搜索

int mex(set<int> &st)               //求mex值
{
    for(int i = 0; ; ++i)
        if(st.find(i) == st.end())
            return i;
}

int sg(int x, int y)                
{
    //不妨设x >= y
    if(x < y) return sg(y, x);
    if(y == 0) return 0;
    if(mp.count({x, y})) return mp[{x, y}];

    set<int> st; 
    //枚举所有后继状态，递归求得该状态SG函数的值
    for(int i = 1; i < x; ++i) st.insert(sg(x - i, i));
    for(int i = 1; i < y; ++i) st.insert(sg(i, y - i));

    return mp[{x, y}] = mex(st);
}

void solve()
{
    int n; cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];

    int ans = 0;
    for(int i = 1; i <= n; i += 2)
    {
        ans ^= sg(a[i], a[i + 1]);
    }
    cout << (ans ? "YES" : "NO") << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _; cin >> _;
    while(_--) solve();
    return 0;
}

后面给出打表代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 9;

int a[N];

map<pair<int, int>, int> mp;

int mex(set<int> &st)
{
    for(int i = 0; ; ++i)
        if(st.find(i) == st.end())
            return i;
}

int sg(int x, int y)
{
    if(x < y) return sg(y, x);
    if(y == 0) return 0;
    if(mp.count({x, y})) return mp[{x, y}];

    set<int> st; 
    for(int i = 1; i < x; ++i) st.insert(sg(x - i, i));
    for(int i = 1; i < y; ++i) st.insert(sg(i, y - i));

    return mp[{x, y}] = mex(st);
}

void table(int n)   //打表
{
    cout << "    ";
    for(int i = 1; i <= n; ++i) cout << setw(2) << i << ' ';
    cout << '\n';
    for(int i = 1; i <= n; ++i)
    {
        cout << setw(2) << i << ' ';
        for(int j = 1; j <= n; ++j)
        {
            cout << setw(2) << sg(i, j) << ' ';
        }
        cout << '\n';
    }
}

void solve()
{
    int n; cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];

    int ans = 0;
    for(int i = 1; i <= n; i += 2)
    {
        ans ^= sg(a[i], a[i + 1]);
    }
    cout << (ans ? "YES" : "NO") << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    table(n);
    // int _; cin >> _;
    // while(_--) solve();
    return 0;
}

从表中不难发现，(感兴趣可以复制上述代码把表打出来看一看)，对于$x$、$y$都是奇数的状态，他们的$SG$值都为$0$。

而对于一个及以上参数为偶数时，状态 { x , y } \{x,y\} {x,y}的$SG$函数值就等于状态$\{(x+1)/2,(y+1)/2\}$的$SG$函数值加上一。

所以最终代码就可以缩短为：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 9;

int a[N];

int sg(int x, int y)
{
    if(x < y) return sg(y, x);
    if((x & 1) && (y & 1)) return 0;

    if(y % 2 == 0) return sg((x + 1) / 2, y / 2) + 1;
    if(x % 2 == 0) return sg(x / 2, (y + 1) / 2) + 1;
}

void solve()
{
    int n; cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];

    int ans = 0;
    for(int i = 1; i <= n; i += 2)
    {
        ans ^= sg(a[i], a[i + 1]);
    }
    cout << (ans ? "YES" : "NO") << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _; cin >> _;
    while(_--) solve();
    return 0;
}