博弈论 - 记录程序和数学的点滴

最后更新于：2022年6月25日下午

2002 年张一飞写过一篇论文《由感性认识到理性认识－透析一类博弈游戏的解答过程》把了这类博弈问题带到了大众视野，在此留下学习笔记（参考了很多的内容：原始论文，codeforces，Wiki，各种博客：小蒟蒻yyb, 自为风月马前卒等等，无法一一列举）

其实我一直想把这个做成自动化的，或者说网页类游戏的，但是一直没有这个精力，而且它们有很多共性，但是由于参数不同很统一，但是不同意又有很多重复代码十分不优雅，而且其实很多游戏都可以混合，所以就会很繁琐

取石子游戏

\(A,B\) 两人面对若干堆石子，按照如下规则取石子

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

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

我们可以用一个 \(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\) 则下面结论显然

若 \(A,B\) 一胜一负，则 \(S\) 胜
若 \(A,B\) 全为负，则 \(S\) 负
若 \(A,B\) 全为胜，则 \(S\) 无法判断（还需要进一步信息才能确定）
若 \(A=B\)，则 \(S\) 负
空局面是负局面

因此根据上面的分解理论，可以将一个局面进行化简。例如 \((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)\) 暴力做法

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;
  }
};

必胜策略代码

#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\) 必须满足：

若 \(f(S) = 0\), 则无论先行者如何取子 \(S \to T\)，都有 \(f(T) \neq 0\)
若 \(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\) 中最小正整数。

Bash game

若最多取 \(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)\)，根据之前的讨论，得知最后的结论。类似地，我们也可以给出代码（这个问题可以做交互题）。

#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] 可变时，也可以考虑，暂时不在此说了。

Fibonacci game

有一堆石子，先手第一次可以取走任意多个（非零且不能取完），以后每人取的石子不能超过上一个的两倍（非零）

先手赢当且仅当石子数不是 Fibonacci 数。

利用 Zeckendorf 定理：任何正整数可以表示为若干个不连续的Fibonacci数之和（数学归纳法可证）

根据这个定理，策略是显然的，对于非 Fibonacci 数 \(n\)，我们找到小于 \(n\) 最大的 Fibonacci 数 \(F_i\)，然后取走 \(n - F_i\) 个数即可。注意到如果石子数一开始就是 Fibonacci 数 \(n\)，那么显然无论怎么操作，它最多只能变成另一个 Fibonacci 数，然后后手直接取完

多堆呢？也能做就是复杂度很高：首先注意到如果去了超过 \(1 / 3\)，那么后手就没有任何限制了，反正问题变成先手后手互换

Multi-Nim

\(n\) 堆石子，从任意一堆中取出任意个非空石子，或者把一堆分成非空的两堆，无法操作者输

\[ sg(x) = \left\{\begin{array}{c} x - 1 & x \equiv 0 \mod 4 \\ x + 1 & x \equiv 3 \mod 4 \\ x & else \end {array} \right. \]

有树上删边游戏

dfs 考虑每个子树的 sg 值，就可以知道父节点这个子树的值了

无法取为胜

甲乙两人面对若干堆石子，其中每一堆石子的数目任意给定, 两人轮流取走一些石子, 每次至少取一枚石子, 每次只能从某一堆中取, 可以取完，最终取完石子的为输家

感性判断

去掉任意多的 0 和偶数个 1 并不会影响结果(是对的, 但是要分情况推敲一下)
无法根据子局面的胜负来判断总局面的胜负.
负局面的价值远远高于胜局面, \((1),(n,n>1),(1,2n,2n+1)\), 奇数个 1, 偶数个 2 是负局面(用数学归纳法容易证明)
从小的开始枚举, 为被负局面包含的极小局面是胜局面, 被所有胜局面包围的是负局面, 这样可以一直进行下去直到得到我们的结果.
前戏终于结束了, 要来真的了 0.0(好害怕)

理性总结

首先我们先剔除所有 0 和偶数个 1 得到新的局面至多有一个 1. 如果为空, 则为胜局面.
对于堆数 \(n=1\) 的情形, \(a1=1\) 为负局面, 其它为胜局面. 对于堆数 \(n>1\) 是若 \(a_1\wedge ⋯\wedge a_n=0\) 为负局面, 其它为胜局面. 证明: 首先证明结论对 \(n=2\) 是成立, 即 \(a_1=a_2\)(不可能同时为 1)时是负局面, 因为 \(a_1=a_2=2\)是负局面, 若 \(a_1=a_2<k\) 是负局面, \(a_1=a_2 = k\), 则下一步必然是 \((a1,a2)=(m<k,k)\) 为胜局面(若 \(m=0,1\) 时显然, 否则下一步 \((a_1=a2)=(m,m)\) 为负局面). 因此结论对 \(n=2\) 成立. 现在若结论对于 \(n<k\) 成立, 那么由引理若 \(a_1\wedge ⋯\wedge a_n=0\) 则下一步必然导致 \(a′_1 \wedge ⋯ \wedge a′_n \neq 0\). 若其中某个 \(a′_i=0\), 那么由归纳法必然导致结论成立. 那么后手就可以取走一些石子导致 \(a′′_1 \wedge ⋯\wedge a′′_n=0\). 另外一出现多于 2 个 1 直接剔除(不会改变异或和的值). 这样下去堆数必然减少, 由归纳法可知结论成立.

有向无环图 DAG 上 SG 问题

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

来自 OI-wiki

对于状态 \(x\) 和它的 \(k\) 个后继状态 \(y_1, y_2, \cdots, y_k\), 定义 SG 函数: \(SG(x) = mex \{ SG(y_1), SG(y_2), \cdots, SG(y_k) \}\)

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

#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;
}

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

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

树上 sg

对了树上问题是这样的，先手确定树上一个点为起点，每次只能到相邻点，到达过的点不能再到达，无法走的输。如果一棵树的树，随便确定一个点为起点，然后就变成有根树的 sg 问题，比 DAG 上还要简单。然后换根 DP，O(n) 能处理，再处理多棵无根树的情况

对于有根树，我们 dfs 搞就好了，也可以参考 DAG 来搞，但是没必要。
对于无根树，我们可以以某一点给根，给树定向，顺便预处理出每个子树的 sg 值，然后下一次 dfs 更新父节点作为子节点的贡献（注意不是父节点的 sg 值），最后再跑一次就可以得到每个点为根的答案了
如果是多棵有根树，十分简单，直接异或和
如果是多棵无根树，那么就每颗树 mex 后（相当于还有一个超级节点），异或和（如下）

之前考虑一个的树上 SG 的问题，如果多颗树不知道怎么解决，转化之后就是下面形式

现在有 m 堆，第 i 堆有 m_i 小堆（每个小堆有非零个石子），每次第一次进入第 i 堆，必须从要在这 m_i 小堆中选择唯一的小堆保留（不取石子），其它小堆（如果有）直接丢掉，然后其它规则与无限制取石子一致

问先手是否有必赢策略

#include <bits/stdc++.h>
#define cerr(x) std::cerr << (#x) << " is " << (x) << '\n'
using LL = long long;

// index start from 0
std::vector<int> sgOnRootedTree(const std::vector<std::vector<int>>& e, int root) {
  int n = (int)e.size();
  std::vector<int> sg(n), cnt(n + 1);
  std::function<void(int, int)> dfs = [&](int u, int fa) {
    for (auto v : e[u]) if (v != fa) dfs(v, u);
    for (auto v : e[u]) if (v != fa) ++cnt[sg[v]];
    int ans = 0;
    while (cnt[ans]) ++ans;
    sg[u] = ans;
    for (auto v : e[u]) if (v != fa) --cnt[sg[v]];
  };
  dfs(root, root);
  return sg;
}
// index start from 0, we should give a dirction for simplify
std::vector<int> sgOnTree(const std::vector<std::vector<int>>& g) {
  int n = (int)g.size();
  std::vector<std::vector<int>> e(n);
  std::vector<int> p(n), sg(n), cnt(n + 2), sgFa(n, n + 1);
  // O(n) since there are exact n - 1 sides
  std::function<void(int)> pdfs = [&](int u) {
    for (auto v : g[u]) if (v != p[u]) {
      p[v] = u;
      e[u].emplace_back(v);
      pdfs(v);
    }
    for (auto v : e[u]) ++cnt[sg[v]];
    int ans = 0;
    while (cnt[ans]) ++ans;
    sg[u] = ans;
    for (auto v : e[u]) --cnt[sg[v]];
  };
  pdfs(0);
  std::function<void(int)> qdfs = [&](int u) {
    ++cnt[sgFa[u]];
    for (auto v : e[u]) ++cnt[sg[v]];
    int now = sg[u];
    while (cnt[now]) ++now;
    for (auto v : e[u]) if (v) {
      if (--cnt[sg[v]] == 0) sgFa[v] = std::min(now, sg[v]);
      ++cnt[sg[v]];
    }
    for (auto v : e[u]) --cnt[sg[v]];
    --cnt[sgFa[u]];
    for (auto v : e[u]) qdfs(v);
  };
  qdfs(0);
  std::function<void(int)> dfs = [&](int u) {
    ++cnt[sgFa[u]];
    for (auto v : e[u]) ++cnt[sg[v]];
    int now = sg[u];
    while (cnt[now]) ++now;
    sg[u] = now;
    for (auto v : e[u]) --cnt[sg[v]];
    --cnt[sgFa[u]];
    for (auto v : e[u]) dfs(v);
  };
  dfs(0);
  return sg;
}
// 多颗树怎么做（每一个堆可以取多种值）
bool sgOnMulTree(const std::vector<std::vector<std::vector<int>>>& g) {
  auto mex = [](std::vector<int> sg) {
    int n = sg.size();
    std::vector<int> cnt(n + 1);
    for (auto x : sg) if (x < n) ++cnt[x];
    int ans = 0;
    while (cnt[ans]) ++ans;
    return ans;
  };
  int ans = 0;
  for (const auto&x : g) ans ^= mex(sgOnTree(x));
  return ans;
}

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  int k;
  std::cin >> k;
  using Node = std::vector<std::vector<int>>;
  std::vector<Node> e(k);
  for (auto &x : e) {
    int n;
    std::cin >> n;
    x.resize(n);
    for (int i = 1; i < n; ++i) {
      int u, v;
      std::cin >> u >> v;
      x[u].emplace_back(v);
      x[v].emplace_back(u);
    }
    for (auto i : sgOnTree(x)) std::cout << i << ' ';
    std::cout << '\n';
    for (int i = 0; i < n; ++i) {
      std::cout << sgOnRootedTree(x, i)[i] << ' ';
    }
    std::cout << '\n';
  }
  std::cout << sgOnMulTree(e) << '\n';
  return 0;
}

阶梯 Nim

有 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 步异或一下。

#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;
}

另一个问题：有 \(n\) 个位置 \(1,\cdots,n\)，每个位置上有 \(a_i\) 个石子。有两个人轮流操作。操作步骤是：挑选 \(1, \cdots, n\) 中任一位置 \(i\)，将至少 1 个石子全部移动至 \(j\) 位置（\(0 \leq j < i\)，且 \(a_{j + 1} = \cdots = a_{i - 1} = 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\) 必输。

#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)\)（\(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 态。所以证毕

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 懂了）。

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)\) 的做法。

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;
  }
};

另一种更快的实现方式：

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;
  }
};

另一种姿势的实现

#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。

// 每次选择在 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;
}

多堆，codeforce 103274G 的变种

有 \(k\) 堆石子 \(n_1, n_2, \cdots, n_k\)(\(\sum n_i \leq N\))，每一个 \(n_i\) 的二进制中 1 的个数都是偶数。每次可以从某一堆 i 中取 \(x_i\) 个，\(1 \leq x_i \leq m_i\)，\(1 \leq m_i \leq M\)，取完之后需要保证剩下的石子的二进制中 1 的个数为偶数，无法取的人输。

使用一个 RingBuffer 和一个 cnt 和一个 mask。需要计算的是 mex（注意到值不会超过 m）

如果 \(m \leq 64\)（注意到二进制中 1 的奇偶性的均匀型，所以 \(m < 128\) 就可以做）, 利用二进制和 __builtin_ctzll 更新 mex，那么 1.5s 内可以做到 \(n < 5 \cdots 10^8\)，提交记录

如果 \(m \leq 1000\), 暂存当前 mex，根据 cnt 更新 mex，那么 1s 可以做到 \(n < 10^7\)，提交记录，注意这里的复杂度为 \(O(n m)\) 很差，但是统计效果很好。

如果 \(m\) 不加限制，其实我们也可以利用 vector<LL> 自己封装的 bitset，用二进制和 __builtin_ctzll 更新 mex，10s 做到 \(n < 10^9, m < 10^8\), 提交记录

所以如果使用上面策略，那么我们可以用 mask 上 mask 就可以常数次搞定答案了～，即 \(m < 64^2\)，我可以搞了。然后再往前嵌套？继续套娃吗？确实可以！

二分图博弈

别人写的挺好

例题：102832H

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

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

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

位置博弈

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

例题：1451D

不公平博弈

surreal Number

直接按顺序看

Matrix67
2009 年集训队论文方展鹏《浅谈如何解决不平等博弈问题》
唐纳德所著的《Surreal Numbers》106 页不推荐

即可，还是很优美的，没啥例题，就 POJ 2931

// 不公平博弈，a[i] 值域为 {1, -1}
double surrealNumber(std::vector<int> a) {
  double r = 0;
  int i = 0, n = a.size();
  while (i < n && a[i] == a[0]) r += a[i], ++i;
  for (double k = 2; i < n; ++i, k *= 2) r += a[i] / k;
  return r;
}
// 模板例题：https://vjudge.net/problem/POJ-2931

横切竖切游戏

先看例题：https://vjudge.net/problem/HDU-3544

切割游戏，这里是题解：https://www.cnblogs.com/AOQNRMGYXLMV/p/4462791.html

从特殊的，小的开始分析，然后，大表找规律，并且不妨假设 \(n \times m, n \geq m\)，\(m = 1\)时，可以切 \(n - 1\) 刀。\(m = 2\) 时，我们发现 \(2 \times 2\) 先切的人吃亏，即局面为 0，切出 \(1 \times 2\) 更吃亏，所以不难看出可以且 \(\frac{n}{2} - 1\) 刀。\(m = 3\) 时，你会发现也是按照 \(m = 2\) 的情况来切，\(m = 4\) 就不一样了。因此不难发现 \(m\) 为 2 的幂次的时候有本质区别。也就是下面的核心代码，证明下次一定把。

int f(int n, int m) {
  bool flag = true;
  if (n < m) {
    flag = false;
    std::swap(n, m);
  }
  int ans = (n >> std::__lg(m)) - 1;
  return flag ? ans : -ans;
}

#algorithm #cpp

五引理上一篇

自然数方幂和公式及其快速算法下一篇