在 2002 年张一飞写过一篇论文 《由感性认识到理性认识-透析一类博弈游戏的解答过程》 从此开启了这类博弈问题的大门,留下学习笔记。

取石子游戏

$A,B$ 两人面对若干堆石子,按照如下规则取石子

  1. 每步至少取一枚石子
  2. 每步只能在某一堆取走部分或者全部石子
  3. 谁无法按照规则取石子,谁就是输家

首先抛开问题,我们先从一般的入手。

我们可以用一个 $n$ 元组 $(a_1,a_2,\cdots,a_n)$ 表示一个局面 $S$。显然 改变 $n$ 元组的顺序仍然是一个局面。

一个局面 $n$ 元局面 $(a_1,a_2,\cdots,a_n)$ 和一个 $m$ 元局面 $(b_1,b_2,\cdots,b_m)$ 之和显然就是一个 $m + n$ 元局面 $(a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_m)$。类似的一个局面也可以有多种分解。

对于局面 $S$,若先行者有必胜策略,则称 “$S$ 胜”;
对于局面 $S$,若后行者有必胜策略,则称 “$S$ 负”。

如果局面 $S$ 胜,则必然存在取子方式 $S \to T$,且 $T$ 负;
如果局面 $S$ 负,则对任意取子方式 $S \to T$,有 $T$ 胜。

局面分解理论,若 $S = A + B$ 则下面结论显然

  1. 若 $A,B$ 一胜一负,则 $S$ 胜
  2. 若 $A,B$ 全为负,则 $S$ 负
  3. 若 $A,B$ 全为胜,则 $S$ 无法判断(还需要进一步信息才能确定)
  4. 若 $A=B$,则 $S$ 负
  5. 空局面是负局面

因此根据上面的分解理论,可以将一个局面进行化简。例如 $(2,2,2,7,9,9)$ 可以化简成 $(2,7)$

而局面分解的关系,很容易让人联想到整数的位运算-异或。

对于上面取石子问题,每一个局面都可以分解成只有一堆石子的局面。
对一个局面,定义一个函数 $f$,然后把它们异或是不是,然后判断是非为 0,作为是否胜的充要条件.这样做是否可行呢?先对原始例子进行实验。

函数 $f$:若局面 $S$ 只有一堆石子,设 $S={a}$,则定义 $f(a) = a$。
设局面 $S = (a_1,a_2,\cdots,a_n)=(a_1)+(a_2)+\cdots (a_n)$,则 $f(S) = f(a_1) \oplus f(a_2) \oplus \cdots \oplus f(a_n)$
我们断言:对于一个局面 $S$,若 $f(S) = 0$,则 $S$ 负,否则,$S$ 胜。

下面证明上面的结论。
引理:$a_1 \oplus a_2 \oplus \cdots \oplus a_n = p \neq 0$,则必存在 $1 \leq k \leq n$,使得 $a_k \oplus p < a_k$。这是因为我们看 $p$ 的最高位,有奇数个$a_k$在此位置非零, 那么与 $p$ 异或后,这一位就从 $1$ 变为 $0$,证毕。

若 $f(S) = 0$,则无论先行者如何取子 $S \to T$,都有 $f(T) \neq 0$。
若 $f(S) \neq 0$,则先行者存在一种取法 $S \to T$, 使得 $f(T) = 0$。这是因为由引理 $a_1 \oplus a_2 \oplus a_n = p \neq 0$,存在 $1 \leq k \leq n$,使得 $x = a_k \oplus p < a_k$。那么我们在第 $k$ 堆取走 $a_k - x$ 个石子,那么 $a_1 \oplus \cdots a_{k - 1} \oplus x \oplus a_{k + 1} \cdots \oplus a_n = p \oplus p = 0$,证毕。

一般 Nim SG 问题的 $O(n^2)$ 暴力做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Nim {
std::vector<int> sg{0};
bool check(int n, int x) {
// 取决于具体问题
return (n & x) == 0;
}
void init(int n) {
std::vector<int> cnt(n + 2);
for (int i = sg.size(); i < n; ++i) {
std::stack<int> S;
for (int j = 1; j <= i; ++j) if (check(i, j)) {
++cnt[sg[i - j]];
S.push(sg[i - j]);
}
int r = 0;
while (cnt[r]) ++r;
sg.emplace_back(r);
while (!S.empty()) {
--cnt[S.top()];
S.pop();
}
}
}
public:
int solve(const std::vector<int> &a) {
init(*std::max_element(a.begin(), a.end()) + 1);
int r = 0;
for (auto x : a) r ^= sg[x];
return r;
}
};

必胜策略代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << "请输入一个正数组,以 0 结尾,输出下一步的必胜策略:" << std::endl;
std::vector<int> a;
int n;
while (std::cin >> n && n) a.emplace_back(n);
int s = 0;
for (auto x : a) s ^= x;
if (s == 0) std::cout << "必败,随便选择一个合理策略吧,等待对手失误吧" << std::endl;
else {
for (auto &x : a) if (x ^ s <= x) {
x ^= s;
break;
}
std::cout << "以下是下一步的一个必胜策略:\n";
for (auto x : a) std::cout << x << " ";
std::cout << std::endl;
}
return 0;
}

这说明了上述想法的可行性。下面把这种思想推广成一般的 SG(Sprague-Grundy)函数的情形

SG 函数

当对石子的取法进行限制时,例如每次最多能去 $m$ 个,或每次最少取 $l$ 个等,此时再令 $f(x) = x$ 就不合适了。那么应该选择怎样的 $f$ 呢。显然 $f$ 必须满足:

  1. 若 $f(S) = 0$, 则无论先行者如何取子 $S \to T$,都有 $f(T) \neq 0$
  2. 若 $f(S) \neq 0$, 则先行者存在一种取子 $S \to T$,使得 $f(T) = 0$。

我们用 $(S) = \lbrace S_1, S_2, \cdots S_k \rbrace$ 表示 $S$ 的下一个可能的局面,定义 $g(S) = \lbrace f(S_1),f(S_2), \cdots f(S_k) \rbrace$,则它必然满足 $f(S) \doteq \text{ MEX } g(S)$

注意上述 $f$ 的值域是整数,$g(S)$ 是整数集的子集。其中 $MEX(A \subseteq \mathbb{N})$ 为不在 $A$ 中最小正整数。

若最多取 $m$ 个没有其它的限制条件,可以取 $f(x) = x \mod m + 1, S = (a_1, \cdots, a_n), f(S) = f(a_1) \oplus \cdots \oplus f(a_n)$

对 SG 感性的理解为,连续最长从赢到输的步数。这样所有的例子都通了!

可以参考 300iq Contest 3E Easy Win 测试。

两人轮流取,第 $k$ 次最少取 $1$ 最多取 $k$,我在 Codeforces 上写了解答,这个可以变形。

假设有 $n$ 堆,每堆有 $x_i$, 并且限制,每次至少取 $l_i$,最多取 $r_i$. 问先手还是后手有必胜策略

经过一番思考,比较 $l_i = 1$ 的 case 可知,若 $l_i \leq x_i \mod (l_i + r_i)$,则此回合有必胜策略。否则必败。观察到 $sg_i(x_i) = \lfloor \frac{x_i \mod (l_i + r_i)}{l_i} \rfloor$(证明是容易的)。然后最后答案就是 $s = sg_1(x_1) \oplus \cdots \oplus sg_n(x_n) \neq 0$。若 $s \neq 0$, 先手有必胜策略:先手可以让 s 变成 0,然后后手无论如何操作,先手让它们的和为 $l_i + r_i$, 然后所有的堆个数都小于超过 $l_i + r_i$ 然后再类似之前的讨论即可。因为如果第 i 堆必败,那么剔除这个堆不会影响最后胜负情况,反之必然满足 $l_i \leq x_i \mod (l_i + r_i) \leq r_i$

因为每次取至少取 $l_i$,因此本质上第 i 堆现在的个数就是 $sg_i(x_i)$,根据之前的讨论,得知最后的结论。类似地,我们也可以给出代码(这个问题可以做交互题)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << "欢迎来到石子游戏,请输入石子的堆数" << std::endl;
int n;
std::cin >> n;
std::vector<int> a(n), l(n), r(n);
std::cout << "请输入石子个数,最少取石子个数,最大取石子个数" << std::endl;
int sg = 0;
for (int i = 0; i < n; ++i) {
std::cin >> a[i] >> l[i] >> r[i];
sg ^= a[i] % (l[i] + r[i]) / l[i];
}
if (sg != 0) {
for (int i = 0; i < n; ++i) {
int t = a[i] % (l[i] + r[i]) / l[i];
if (sg ^ t <= t) {
a[i] -= t * l[i];
std::cout << "第 " << i + 1 << " 堆中取 " << l[i] * t << " 个" << std::endl;
break;
}
}
std::cout << "当前石子情况为:" << std::endl;
for (auto &x : a) std::cout << x << " ";
std::cout << std::endl;
} else {
std::cout << "当前无必胜策略,随便取一个合理的取法,等待对手失误吧" << std::endl;
}
return 0;
}

l[i]r[i] 可变时,也可以考虑,暂时不在此说了。

有向无环图上 SG 问题

在一个有向无环图中,只有一个起点,上面有一个棋子,两个玩家轮流沿着有向边推动棋子,不能走的玩家判负。

来自 OI-wiki

对于状态 $x$ 和 它的 $k$ 个后继状态 $y_1, y_2, \cdots, y_k$,定义 SG 函数:

而对于由 $n$ 个有向图游戏组成的组合游戏,设它们的起点分别为 $s_1, \cdots, s_n$,先手必胜当且仅当 $SG(s_1) \oplus \cdots \oplus SG(s_n) \neq 0$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

int SG() {
// n 个节点,0 为起点,m 条有向边,确保无环。
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int>> e(n);
for (int i = 0; i < m; ++i) {
int x, y;
std::cin >> x >> y;
e[x].emplace_back(y);
}
std::vector<int> sg(n, -1);
std::function<int(int)> dfs = [&](int u) -> int {
if (sg[u] != -1) return sg[u];
std::set<int> S;
for (auto v : e[u]) S.insert(dfs(v));
sg[u] = 0;
while (S.find(sg[u]) != S.end()) ++sg[u];
return sg[u];
};
return dfs(0);
}

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int nroot;
std::cin >> nroot;
int ans = 0;
while (nroot--) {
ans ^= SG();
}
std::cout << (ans ? "先手赢" : "后手赢") << std::endl;
return 0;
}

可以做到二维平面上有障碍点集,又可以做一个题目了。

注意到上述问题,堆与堆之间是相互独立的,如果不独立,那就很难考虑了。

移动石子

有 m 堆石子 $(a_1, \cdots, a_m)$ 每次可以从 i 位置移动 $1 \leq c_i \leq a_i$ 个石子到 i - 1 的位置。两人轮流进行,无法移动者输。

观察到偶数位置的石子不会影响结果(因为某人移动偶数位置石子,另一个人总能把移动的石子再次移动到偶数位置。因此最终结果其实就是 $a_1 \oplus a_3 \cdots$ 非零则先手赢,否则后手赢。

这个问题可以到树上做!也是类似的,每个点只能移动到它的父节点。还能拓展到每次移动到 k-祖先。还能拓展到换根的情形。例题:1498F,那么我们每 2k 步异或一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

int main() {
//freopen("in", "r", stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, k;
std::cin >> n >> k;
int k2 = k * 2;
std::vector<std::vector<int>> e(n);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
--x; --y;
e[x].emplace_back(y);
e[y].emplace_back(x);
}
std::vector<int> a(n);
for (auto &x : a) std::cin >> x;
std::vector<std::vector<int>> b(n, std::vector<int>(2 * k)); // 以 u 为节点的子树的答案
auto c = b; // c 表示父节点当作儿子节点时,这个分支上的答案
std::function<void(int, int)> preDfs = [&](int u, int fa) {
b[u][0] = a[u];
for (auto v : e[u]) if (v != fa) {
preDfs(v, u);
for (int i = 0; i < k2; ++i) {
b[u][(i + 1) % k2] ^= b[v][i];
}
}
};
preDfs(0, 0);
std::vector<int> ans(n);
std::function<void(int, int)> dfs = [&](int u, int fa) {
for (int i = k; i < k2; ++i) {
ans[u] ^= b[u][i] ^ c[u][i];
}
for (auto v : e[u]) if (v != fa) {
for (int i = 0; i < k2; ++i) {
c[v][(i + 1) % k2] = c[u][i] ^ b[u][i] ^ b[v][(i + k2 - 1) % k2];
}
dfs(v, u);
}
};
dfs(0, 0);
for (auto x : ans) std::cout << std::min(1, x) << ' ';
std::cout << '\n';
return 0;
}

不公平取石子的游戏

NewCoder 上有个不公平的游戏:A 每次能取 [1, p] 个石子,B 能取 [1, q] 个石子,A 先。

显然 $p = q$ 时,就是之前的经典问题。只需考虑 n % (p + 1) 即可。若 $p > q$,那么 A 必胜,因为此时 $p \geq q + 1$,所以有必胜策略(策略一:总能让剩余的为 0 或者 大于 p;策略二:若 n % (p + 1) 不为 0 就按照 q = p 处理,否则 A 第一次取 p + 1),若 $p < q$,只有 A 取完则赢,否则必输。

m 堆,

  • $p = q$,经典问题,前面有结论。
  • $p > q$,若存在 $a_i$ 使得 $a_i > q$ 或 $a_1 \oplus \cdots \oplus a_m \neq 0$,则 A 必赢。
  • $p < q$,若存在大于一个 $a_i$ 使得 $a_i > p$,$A$ 必输。若所有 $a_i \leq p$ 那么就等于无限制。所以我们只需考虑,有唯一的一个 $a_i > p$ 的情形,$x = \oplus \cdots a_{i-1} \oplus a_{i + 1} \cdots \oplus a_m$,若 $x = 0$ 或者 $x \oplus a_i > p$ 或者 $x - x \oplus a_i > p$ 则 $A$ 必输。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

bool win(const std::vector<int> &a, int p, int q) {
int sg = 0, n = a.size();
if (p > q) {
for (int i = 0; i < n; ++i) if (a[i] > q) return 1;
for (auto x : a) sg ^= x;
} else if (p == q) {
for (auto x : a) sg ^= x % (1 + p);
} else {
int ai = -1;
for (auto x : a) {
sg ^= x;
if (x > p) {
if (ai != -1) return 0;
ai = x;
}
}
if (ai != -1) {
int aii = sg ^ ai;
return aii <= p && aii <= ai && ai - aii <= p;
}
}
return sg;
}

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, p, q;
std::cin >> n >> p >> q;
std::vector<int> a(n);
for (auto &x : a) std::cin >> x;
std::cout << (win(a, p, q) ? "first player win" : "second player win") << std::endl;
return 0;
}

多人博弈:合作,收买,间谍

  • 如果不考虑合作策略,那么就会变成不公平的二人博弈游戏,可能出现没人有必胜策略。
  • 如果考虑合作,那就有意思了,也复杂多了,这时候还有明面合作和暗面合作,还有就是间谍。

知乎

m 个人 $m > 2$($m = 2$ 就回到了普通的二人博弈情况),每个人可取 $a, b$($a = b$ 是平凡的,没有考虑的意义)。先取到 n 者赢。

当 n 充分大时,超过 $\lfloor \frac{m}{2} \rfloor$ 合作,则此群体必胜,即单个人没有必赢策略。rt237 给的证明十分漂亮。还可以考虑反问题:即先取到 n 者输。

无限制取石子问题的反问题

一堆石子谁先取到最后一个谁输!,该问题在 已经介绍了。做法:

首先剔除所有的 0,以及偶数个 1,并不会影响局面的胜负。空局面认为是胜。若此时堆的个数为 1,那么 $a_1 = 1$ 为输局面,其它为赢局面。如果堆数 $n > 1$。那么 $a_1 \oplus \cdots \oplus a_n = 0$ 为输局面,否则为赢局面。(首先对 $n = 2$ 数学归纳证明,然后对一般的 n 数学归纳证明。

有顺序堆的取石子问题

例题:1382B。即看那一步有必赢且必输的策略。

如果此题加限制条件,每次最多取 $m$ 个,那么答案就是第一个 $\mod (m + 1)$ 大于 1 的数。但是要注意 取模后为 0 的情形。

每次可取多堆

例题:1451F

更多博弈问题可见:Codeforces-game

sg 函数是因子个数 + 1

例题:codeforce gym 102911C,从 $n$ 中取 $k$ 个满足 $k > 0$ 且 $n - k$ 是 $n$ 的因子。设 $n = p_1 ^{s_1} \cdots p_r^{s_r}$, 则 $sg(n) = s_1 + \cdots s_r + 1$。

一堆,相邻之间有限制

$n$ 个元素,每次最少取 $1$,最多取 $m$ ($m \geq 2$),且相邻两个的和不能为 $m + 1$。谁无法取谁输。

结论 n % (m + 2) == 0 则先手必输,反之先手必赢。

证明:
首先不难看出若 $n \leq m + 1$ 时,先手必赢,$n = m + 2$ 时,先手必输。

  • 若第一步先手取 1,那么后手取 m - 1,此时先手不能取 2(所以先手无法取完),若第二步先手取 1,那么后手取 1回到最初的情况(那么剩下的数为 $n - m - 2$ 又满足 n % (m + 2) == 0)。若第二步先手取 3,那么后手取 $m - 1$ (此时又回到了第一步的情况,再继续考虑第二步即可)。若 第二步先手取 $x$($x \geq 4$), 后手取 $m + 4 - x$ 就回到了最初的情况。
  • 若第一步先手取了 x ($x \geq 2$) 那么后手取 $m + 2 - x$ 即可。

反之 k = n % (m + 2), $k \neq 0$,若 $k \leq m$,那么先手取 $k$ 即可。否则 $k = m + 1$, 那先手取 $m$,此时后手不能取 $1$,因此后手取完之后,剩下的数依然满足 $n \mod (m + 2) \neq 0$。

一堆,取的取走的需要和原来是数字与运算为 0

当前 $n$,每次取 $1 \leq x \leq n, x \And n = 0$。无法取的输。

首次在 Codeforces 上看到,我评论 种给出了答案。首先观察到后置 1 并不影响答案,打表观察发现到,F:若所有的 11 成对挨着出现(否则记作状态 T),那么先手输,否则先手赢。先删去后置的 1,不妨假设 $n$ 为偶数,如果我们在状态 F,那么我们看第一次成对 11 出现变化的位置,此时第一个 1 肯定不会变动,也就导致了 11 不成对出现;如果我们在状态 T,如果 1 的个数为奇数,那么我们就把最后一个 1 移动到最后(相当于删除了),然后让奇数个 1 向它右边的 1 靠拢(从左到右数)。至此说明 F 的下一步状态必为 T,T 存在一个到 F 的状态。且初始态 $n = 0$ 为 F 态。所以证毕

1
2
3
4
5
6
7
8
9
10
11
12
13
bool solve(LL n) {
while (n & 1) n >>= 1;
while (n) {
n >>= __builtin_ctzll(n);
bool flag = false;
while (n & 1) {
n >>= 1;
flag = !flag;
}
if (flag) return true;
}
return false;
}

多堆,取的取走的需要和原来是数字与运算为 0

为了给群友解释,重新写一次。

有 $m$ 堆石子 $n_1, \cdots, n_m$,每次可以在其中一堆(比如第 $i$ 堆)中取 $x_i$ 个石子,且满足 $1 \leq x_i \leq n_i, x_i \And n_i = 0$,无法取的人输,两人轮流游戏,且都以最优策略进行。问先手赢还是后手赢。

首先如果没有 $x_i \And n_i = 0$ 这个限制。那么这就是最经典的 nim 取石子游戏。先手赢当且仅当 $n_1 \wedge \cdots \wedge n_m \neq 0$(这个可以从张一飞的集训队论文中找到解释)。上述问题也是经典的 SG nim 游戏的一种特殊情况有一般性的做法:

(仅需考虑一堆的情况)设 $k_1, k_2, \cdots k_r$ 为所有 $n$ 的合理的下一步可能那么 $sg(n)$ 就定义成 $MEX(sg(k_1), \cdots, sg(k_r))$(即未出现的最小的非负整数),其中 $sg(n) = 0$,表示 $n$ 个石子时,先手输。若 $sg(n) \neq 0$ 那么先手必然存在一个策略 $k_i$ 使得 $sg(k_i) = 0$(这是 MEX 的定义可推出)。这就给出了 sg 函数。先手赢当且仅当 $sg(n_1) \wedge \cdots \wedge sg(n_m) \neq 0$。

可以用上述方法证明如果没有 $x_i \And n_i = 0$ 这个限制,$sg(n) = n$。如果把限制改成 $1 \leq x_i \leq \min(M, n_i)$ 那么 $sg(n) = n \mod (M + 1)$。这些都是经典结果。

我们回到原来的问题:仅需考虑一堆的情况,即 $n$ 个石子,每次取 $x$ 个满足 $1 \leq x \leq n, x \And n = 0$。首先观察到输赢仅与 $n$ 的二进制表示有关,且我们删除后置的 1 不会影响结果。对于上述问题,我无法给它的 sg 一个简单的表达式,我打表观察(用 bitset)规律也没有观察出个啥。只知道 $sg(n) \neq 0$ 当且仅当 $n$ 的二进制中存在 0(奇数个连续的 1)0 这种形式的子串。即我仅仅知道一堆的情况下,谁会赢。我打完表就不期待这个问题 sg 有简单的表达式了,能有一个 $O(\log n)$ 或者 $O(\log^2 n)$ 的做法就万幸了,所以需要各位群友大大的帮助!

我在 codeforces 上也提了这个问题,希望群友大大们能抬一手不要让它淹没于大海。

wery0 给了一个 $O(n^{\log_2 3})$ 的做法(一开始不理解,后来根据他的 Talk 懂了)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Nim {
std::vector<int> sg{0}, cnt;
public:
int reverseBit(int n) {
return n ^ ((1 << 32 - __builtin_clz(n)) - 1);
}
void init(int n) {
if (sg.size() >= n) return;
cnt.resize(n + 2);
for (int i = sg.size(); i < n; ++i) {
if (i & 1) {
sg.emplace_back(sg[i >> 1]);
continue;
}
int m = reverseBit(i);
for (int j = m; j; j = (j - 1) & m) {
++cnt[sg[i - j]];
}
int r = 0;
while (cnt[r]) ++r;
sg.emplace_back(r);
for (int j = m; j; j = (j - 1) & m) {
--cnt[sg[i - j]];
}
}
}
int solve(const std::vector<int> &a) {
init(*std::max_element(a.begin(), a.end()) + 1);
int r = 0;
for (auto x : a) r ^= sg[x];
return r;
}
};

wery0 给了一个 $O(n^{\log_2 3} \log n)$ 的做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Nim {
std::vector<int> sg{0};
public:
int f(int n, int x) {
int r = n;
for (int i = 1; i < n; i *= 2) if ((n & i) == 0) {
if (x & 1) r -= i;
x /= 2;
if (x == 0) break;
}
if (x > 0) return -1;
return r;
}
void init(int n) {
for (int i = sg.size(); i < n; ++i) {
if (i & 1) {
sg.emplace_back(sg[i >> 1]);
continue;
}
std::set<int> S;
for (int j = 1; j < i; ++j) {
int now = f(i, j);
if (now < 0) break;
S.insert(sg[now]);
}
int r = 0;
while (S.count(r)) ++r;
sg.emplace_back(r);
}
}
int solve(const std::vector<int> &a) {
init(*std::max_element(a.begin(), a.end()) + 1);
int r = 0;
for (auto x : a) r ^= sg[x];
return r;
}
};

另一种更快的实现方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Nim {
std::vector<int> sg{0};
public:
int f(int n, int x) {
int r = n;
for (int i = 1; i < n; i *= 2) if ((n & i) == 0) {
if (x & 1) r -= i;
x /= 2;
if (x == 0) break;
}
if (x > 0) return -1;
return r;
}
void init(int n) {
if (sg.size() >= n) return;
std::vector<int> cnt(n + 2);
for (int i = sg.size(); i < n; ++i) {
if (i & 1) {
sg.emplace_back(sg[i >> 1]);
continue;
}
std::stack<int> S;
for (int j = 1; j < i; ++j) {
int now = f(i, j);
if (now < 0) break;
++cnt[sg[now]];
S.push(sg[now]);
}
int r = 0;
while (cnt[r]) ++r;
sg.emplace_back(r);
while (!S.empty()) {
--cnt[S.top()];
S.pop();
}
}
}
int solve(const std::vector<int> &a) {
init(*std::max_element(a.begin(), a.end()) + 1);
int r = 0;
for (auto x : a) r ^= sg[x];
return r;
}
};

另一种姿势的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

template<int N>
class Nim {
std::vector<int> sg, cnt;
public:
Nim() : sg(N), cnt(N + 2) {
for (int i = 1, msk = 0, m; i < N; ++i) {
if (i & 1) {
sg[i] = sg[i >> 1];
continue;
}
if ((i & -i) == i) msk = i * 2 - 1;
m = msk ^ i;
for (int j = m; j; j = (j - 1) & m) {
++cnt[sg[i - j]];
}
int r = 0;
while (cnt[r]) ++r;
sg[i] = r;
for (int j = m; j; j = (j - 1) & m) {
--cnt[sg[i - j]];
}
}
}
int solve(const std::vector<int> &a) {
int r = 0;
for (auto x : a) r ^= sg[x];
return r;
}
};

int main() {
// freopen("in", "r", stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
auto start = std::clock();
const int N = 1e5 + 2;
Nim<N> A;
int n;
std::cin >> n;
std::vector<int> a(n);
for (auto &x : a) std::cin >> x;
std::cout << A.solve(a) << "\n";
std::cout << "Time used: " << (std::clock() - start) << "ms" << std::endl;
return 0;
}

多堆,取的取走的需要和原来是数字或运算为自己

显然 sg(n) = __built_in_popcount(n)

每次可以取小于 m 堆中的任意多个元素(不能一个不取)

做法:考虑二进制,对于任意给定位,这一位的 1 的个数和都是 m 的倍数,那么就后手赢,否则先手赢。

对于否则的情况,我们总可以找到考虑最高位不是 m 的倍数,然后随便选择余数个(当前位为 1 的)进行改变。并且这些数后面的位是可以任意改变的。然后再继续往低位跑,显然,最终选取的个数总和小于 m。

1
2
3
4
5
6
7
8
9
10
11
// 每次选择在 x 堆(0 < x < m) 取石子,不能取的输
bool multNim(const std::vector<LL> &a, int m) {
LL mx = *std::max_element(a.begin(), a.end());
int ln = std::__lg(mx + 1) + 1;
for (int i = 0; i < ln; ++i) {
int cnt = 0;
for (auto x : a) if ((x >> i) & 1) ++cnt;
if (cnt % m) return true;
}
return false;
}

二分图博弈

别人写的挺好

例题:102832H

先手必胜当且仅当任何一个最大匹配方案都包含初始状态。

判定: 不加入初始节点,跑一遍最大流,加入初始节点,再跑一次最大流,有变化所以先手必赢。

另外如果先手可选择初始状态(进入算一次),那么先手输当且仅当图是完全匹配。

位置博弈

只能朝着几个方向走,走出区域者输

例题:1451D