有向图游戏与sg函数

HeJie2026-04-212026-09-17

有向图游戏是一个经典的博弈游戏——实际上，大部分的公平组合游戏都可以转换为有向图游戏。在一个有向无环图中，只有一个起点，上面有一个棋子，两个玩家轮流沿着有向边推动棋子，不能走的玩家判负。

By : OI Wiki

mex 函数

：不属于集合的最小非负整数。例如、。

SG 函数

对于状态和它的所有个后继状态，定义函数：

什么时候结束游戏： 定义没有后继状态的为必败态，也就是函数为的状态，此时函数的值一定为。

一个简单的巴什博弈问题： 有个石子，小 A 先取，小 B 后取，可以取一颗或者两颗石子，不能不取，最后取的人失败，两人都非常聪明，问谁获胜。

此问题符合对有向图游戏的定义。

如果将每个状态视为一个节点，可以转化为一个博弈图：

联系上方说过的对必败态的定义，。

并且由此可以递归地得到所有点的值：

然后惊奇的发现，在这个博弈图中，等于时小 A 败，不等于时小 A 胜。

推广一下，就是余不等于的时候小 A 胜，否则小 B 胜。

if (n % 3 == 1) cout << B << endl;
else cout << A << endl;

链接： https://www.zhihu.com/question/445147447/answer/1740176817

SG 定理

定义

例题: POJ2311 Cutting Game

参考：G60 有向图游戏 SG函数【博弈论】董晓

在这道题中，每次操作会造成两个状态，比如一个 4 * 3 的纸张可以被剪为 1 * 3 和 3 * 3 的、2 * 3 和 2 * 3 的等状态。

我们把每个的纸张看作一个节点，用表示。值被定义为。用来表示博弈图中子节点代表的值。

$或$

我们看到最先剪出的人获胜，所以在本题中，将没有后继状态的设置为必败态不合适。可以看出与对于先取的人来说一定是必胜态。那么对应的，剪出与的一定是必败态。所以本题中的必败态（也就是边界）设置为、、、。因为这些状态一定能剪出必胜态。再递归地得到每个节点的值。

#include <bits/stdc++.h>

using namespace std;

void solve(int w, int h) {
    vector<vector<int>> sg(w + 1, vector<int> (h + 1, -1));

    sg[1][1] = 0;
    auto get = [&](auto self, int x, int y) {
        if (~sg[x][y]) return sg[x][y];

        set<int> S;

        for (int i = 2; i <= x - 2; i ++) {
            S.insert(self(self, i, y) ^ self(self, x - i, y));
        }

        for (int i = 2; i <= y - 2; i ++) {
            S.insert(self(self, x, i) ^ self(self, x, y - i));
        }

        for (int i = 0; ; i ++) {
            if (!S.count(i)) {
                return sg[x][y] = sg[y][x] = i;
            }
        }
    };

    cout << (get(get, w, h)? "WIN" : "LOSE") << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int w, h;
    while (cin >> w >> h) {
        solve(w, h);
    }

    return 0;
}

小凯取石子

参考

首先如果将概率之类的提问放到一边，计算只能取个或个，这种问题对应的数，得到（从开始）：（存在一个长度为的循环节）。

可以假设 Kc0 取完个石子和取完个石子后，再计算答案。当值不为的时候，无论之后 Kc0 选什么小凯一定赢。依据这个，让足够大再看各个值的情况：

：从和来，一定为。
：从和来，有的概率一定赢，另外由之前的概率递推来。
：从和来，一定为。
：从和来，有的概率一定赢，另外由之前的概率递推来。
：从和来，有的概率一定赢，另外由之前的概率递推来。

计算一到五小凯赢的概率：, , , , 。之后可以推导出一个式子：

然后经过推导与找规律，得到答案。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 998244353;

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

void solve() {
    ll n;
    cin >> n;
    auto t = n / 5;
    if (n == 1) cout << 499122177 << '\n';
    else if (n % 5 == 2 || n % 5 == 0) cout << 1 << '\n';
    else if (n % 5 == 1) cout << (1 + mod - qmi(qmi(2, mod - 2), t)) % mod << '\n';
    else if (n % 5 == 3) cout << (1 + mod - qmi(qmi(2, mod - 2), t + 2)) % mod << '\n';
    else cout << (1 + mod - qmi(qmi(2, mod - 2), t + 1)) % mod << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll t;
    cin >> t;

    while (t --) {
        solve();
    }

    return 0;
}