零、前言
NOIP2024 挂大分了。
fz $\to$ xm 为了防止心态崩溃就找了个专题学学转移注意力。
往事流转 在你眼眸
一边遗忘 一边拼凑
如我虔诚 合十双手
唯愿你能 得到拯救
一、博弈论基础
定义
对于一个游戏局面，有两个玩家 $A,B$ 分别对它操作，最后的结果是先手必胜或后手必胜，双方的操作方式和目的相似。
本文将必胜态记为 $S$，必败态记为 $T$。
- 必胜态：当前游戏局面存在至少一种操作方案使得游戏局面变为必败态。
- 必败态：当前游戏局面的所有操作方案都会使得游戏局面变为必胜态。
- 子游戏：将原游戏拆分成若干个同时进行的游戏，可以随机挑选一个子游戏进行操作。
Nim 游戏
给定 $n$ 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
二、一些常用思想
1. 从最简单情况开始思考
对于 Nim 游戏进行分析。
这里约定用 $\{3\}$ 表示总共有 $1$ 堆石子，这堆石子有 $3$ 个，同理 $\{2,3\}$ 表示有 $2$ 堆石子分别为 $2,3$ 个。
- 最简单的是 $n=1$，显然先手必胜。
- 然后考虑 $n=2$，最简单的是两堆石子相等，这里开始变得较为复杂了，所以引入第二种思想。
2. 后手抵消先手
即后手可以通过模仿先手的操作，使得先手的操作无效。
- 对于 $n=2$ 石子数量相等的情况，设两堆分别为 $A,B$。先手在 $A$ 拿走 $x$ 个，则后手也在 $B$ 拿走 $x$ 个。
- 此时后手可以通过这样的操作保证两堆石子数量相等，到最后一定是先手必败。
- 否则显然是先手必胜，因为先手可以先进行一步操作使得后手面临两堆石子相等的必败态。
3. 子游戏
- 如果一个局面是 $\{T,T\}$，即两个子游戏都是必败态，那么显然先手必败。
- 假设先手任意选择一个子游戏进行操作，则后手陪它玩这个子游戏，直到先手输了操作另一个子游戏，最后一定先手必败。
- 如果局面是 $\{S,T\}$ 或 $\{T,S\}$ 呢？
- 先手一定能通过操作一次 $S$ 使得局面变为 $\{T,T\}$。
- 即后手必败，先手必胜。
- 如果局面是 $\{S,S\}$ 又会怎样呢？
- 这并不确定。
- 首先注意一下必胜态可以转移到必败态，也可以转移到必胜态。
- 先手一定不会选择转移到必败态，因为转移后 $\{S,T\}$ 就会使得后手必胜，先手必败。
- 然而一个必胜态有多少个后继必胜态是未知的，所以无法确定。
这里重新思考一下，令 $S=1,T=0$，则有：
- $\{S,T\} \to S, \{1,0\} \to 1$。
- $\{T,S\} \to S, \{0,1\} \to 1$。
- $\{T,T\} \to T, \{0,0\} \to 0$。
- $\{S,S\} \to ??, \{1,1\} \to ??$。
这个东西看上去很像或运算或者异或运算。
这里直接给出结论：所有石子数量异或和如果是 $0$ 先手必败，否则先手必胜。
三、SG 函数（重点）
对于任意一个子游戏 $u$，定义 $sg(u) = mex \{sg(v) | u \to v \}$，$u \to v$ 表示可以从 $u$ 局面转移到 $v$ 局面，$mex$ 表示集合内未出现的最小非负整数。
Nim 游戏可以直接异或的原因是 $sg(u)=u$，实际上是做 $sg(u)$ 的异或和。
为什么 $sg(u)=u$？因为 $u \to v$ 中 $v$ 满足 $0 \leq v \lt u$，所以 $sg(u) = mex \{sg(v)\} = u$。
对于一个游戏局面，如果所有子游戏的 $sg$ 异或和为 $0$，则先手必败，否则先手必胜。
四、解题思路
1. 暴力求解 sg 值
按照定义和题目大意做，对每个局面记一个 $mex$ 桶，依靠后继状态求出每个局面的 $sg$ 值。
例题：POI2000 Stripes
有一排石子共 $L$ 个，两人交替操作，每次可以选连续一段 $A,B$ 或 $C$ 个石子，不能取石子的输，问先手是否必胜。
$L,A,B,C \leq 100$。
SG 板子题，直接枚举局面，枚举选 $A,B,C$，枚举从哪里开始选，然后分割成左右两个子游戏做，异或得到 $sg$ 值。
2. 拆分为子游戏
- 如何设计子游戏？
- 如何求出子游戏的 $sg$ 值？
- 把子游戏合并。
例题：P3185 [HNOI2007] 分裂游戏
首先第一个问题是：怎么设计 $sg$ 值？
首先观察到：如果设 $sg(x)$ 表示一堆 $x$ 个石子。但显然会出现一个问题：在第一堆和在最后一堆的 $x$ 个石子它的意义是不一样的，因为分裂往后放的选择和机会都不均等。
而且这题和 Nim 游戏不一样，首先它可以加石子，而 Nim 只能减；其次这题跟位置有关。
考虑后手抵消先手，设先手从 $i$ 拿，在 $j,k$ 放，那么后手也这么做，于是这就和奇偶性相关。
后手可以一直模仿先手直到先手把唯一一颗石子拿走。这意味着如果后手可以一直模仿先手，那么就必胜，因为先手每次操作完后手一定能操作。
综上，在第 $i$ 堆取石子，有 $2$ 个和有 $4$ 个本质上是相同的，即只需要考虑奇偶性。
那么 $a_i$ 序列就变成了 $01$ 序列，表示偶数或奇数。
既然答案和位置有关系，那么就设 $sg(i)$ 表示一个石子在 $i$ 位置的 $sg$ 值。
（这里 $a_i$ 已经对 $2$ 取模）对于 $a_i=0$，肯定不改变后面石子的奇偶性，因为后手不断模仿先手。
对于 $a_i=1$ 呢？枚举 $j,k$，然后把 $sg(j),sg(k)$ 异或扔进桶里做 $mex$。
$n \leq 21$。这显然可以枚举 $i,j,k$ 算 $sg$ 值。
做完了吗？还要知道第一步有多少种取法，怎么取。
从初始状态枚举每个状态，看哪些状态 $sg$ 是 $0$（即必败态），然后暴力枚举求方案数。
3. 转化为 Nim 游戏
例题：Northcott Game
有一个 $n$ 行 $m$ 列（$1 \leq n \leq 1000, 2 \leq m \leq 100$）的棋盘，每行有一个黑棋子（先手）和一个白棋子（后手），每次可以把某一行自己的棋子移动到同一行任意一格，但不能越过对方的棋子。不能移动的人输，求先手是否必胜。
Nim 游戏的变种。观察到如果黑棋和白棋紧贴，黑棋先手，那么白棋只需要接着紧贴黑棋（后手模仿先手）即可。
所以把 $abs(x-y)-1$ 作为这一堆石子的数量，做 Nim 游戏即可，其中 $x,y$ 分别为这一行中黑棋和白棋的位置。
4. 找规律
求解 $sg$ 函数复杂度太高时可以通过找规律降低复杂度。
例题：A Simple Nim
有 $n$ 堆石子，两人轮流操作，可以任选操作类型，操作有两种：
1. 把一堆 $\geq 3$ 的石子分为三堆。
2. 从一堆石子内取走若干个。
有 $T$ 组多测，$T \leq 100, 1 \leq n \leq 10^6, 1 \leq a_i \leq 10^9$。
$a_i$ 太大了，所以打表找规律，然后直接干即可。
例题：巴什博弈
本质上也是推 SG 函数然后找规律。
