帆软杯武汉大学新生赛 I 犹太棋（博弈，SG函数）

题目链接

题意

"犹太棋"是一种经典的巴什博弈游戏，本题的游戏由其玩法改编而来。你并不需要了解关于"犹太棋"的知识，只需要仔细阅读以下的规则说明：

有一个长为 \(n\) ，宽为 \(1\) 的棋盘，现在给定一个初始局面，某些地方已经有了棋子， \(Alice\) 选手和 \(Bob\) 选手开始下棋，双方轮流行动， \(Alice\) 先手。

每一次，当前行动的人可以选择连续的一段、没有棋子的、长度不大于 \(3\) 的 \(x\)个位置，将这些位置都放上一枚棋子，最先不能操作的人判负。

现在 \(Alice\) 想要知道，如果双方都足够聪明，她是否是先手必胜的？

如果是，输出\(YES\)；否则，输出\(NO\)。

其中，\(0\leq n\leq 3000\)。

做法

比较显然是用\(SG\)函数做，已经放置了棋子的地方把棋盘分为了几个连续段，等价于把一个游戏分成了多个子游戏。
根据\(SG\)定理，总的游戏的\(SG\)函数值等于所有子游戏\(SG\)函数值的异或和。

·对于每次操作，可以取长度为\(1/2/3\)的连续一段放上棋子，相当于把连续的一段分为\(1/2\)段，也就是一个游戏分为\(1/2\)个子游戏。
分为\(1\)个长度为\(k\)的子游戏可以看作是分为一个长度为\(0\)的子游戏和一个长度为\(k\)的子游戏,所以每一次操作都可以看做把一个游戏分为两个子游戏。
根据SG定理，\(SG_{x}=mex\{S=(SG_{i}\ Xor\ SG_{j})|i + j = x - k, k = 1/2/3\}\)。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
void solve() {
    int n; string s; cin >> n >> s;
    vector<int> sg(n + 1, -1);
    sg[0] = 0; sg[1] = 1; sg[2] = 2;
    auto get = [&](auto self, auto &sg, auto x) {
        if (sg[x] != -1) return sg[x];
        set<int> s;
        for (int i = 1;i <= 3;i++) {
            for (int j = 0;j <= x - i;j++) {
                if (x - i - j >= 0)
                s.insert(self(self, sg, j) ^ self(self, sg, x - i - j));
            }
        }
        for (int i = 0; i < n + 2;i++) {
            if (s.find(i) == s.end()) {
                sg[x] = i;
                break;
            }
        }
        return sg[x];
    };
    int ans = 0;
    for (int i = 0;i < n;i++) {
        if (s[i] == '0') {
            int j = i;
            while (j < n - 1 and s[j + 1] == '0') j ++;
            int len = j - i + 1;
            ans ^= get(get, sg, len);
            i = j;
        }
    }
    
    cout << (ans ? "YES\n" : "NO\n");
    
}

signed main(void) {
    cin.tie(nullptr), cout.tie(nullptr) -> ios::sync_with_stdio(false);
    solve(); 
    return 0;
}