OI博弈论的若干模型
OI 不是知识竞赛。
平等博弈是完全信息的（知道双方目标及操作收益），交替行动的，知道当前局面和转移的，平等（决策和当前状态操作者无关）的。
不平等博弈和上面一致，但是有一方更加平等。
所有的平等博弈都可以化为 DAG 上的移动游戏。
公平组合游戏是无法行动者败的游戏。这样的游戏每个状态具有结果类 \(\mathcal{N,P}\)，分别代表先手必胜和先手必败。
若干简单游戏
DAG 上的移动游戏
有一张有向无环图, 其中一个节点上有一个棋子. 从 Alice 开始游戏, Alice 和 Bob 轮流将这个棋子沿着一条有向出边移动, 无法移动者判负. 问最后谁会获胜。
注意到这是一个平等博弈, 于是只用考虑先手必胜/必败. 于是按照拓扑排序的方式递推出当前棋子在每个节点时对应先手必胜/先手必败即可。
Ferguson Game
有两堆石子分别 \(n,m\) 个, 双人博弈, 每次操作是清空其中一堆石子并将另一堆石子分成任意非空的两堆新的石子. 无法操作者输，问最后谁会获胜。
先手必败当且仅当 \(2\not\mid n,m\)，可以归纳证明。
Chomp Game
有一个 \(n\times m\) 的网格，每个人可以选择还有的格子 \((a,b)\)，然后把 \((x',y'),\forall x'>a,y'>b\) remove 掉。无法操作者输，问最后谁会获胜。
先手必败当且仅当 \(n=m=1\)。
证明：
先手可以通过选取必然被后面包含的 \((n,m)\) 来 pass 一步。
如果先手是必败的，选择对手的选择即可。
网易车 Game
买车和买 qq 超级会员。
先手必胜当且仅当其买车。
Bash Game
有一堆石子共 \(n\) 个, 双人博弈, 每次从石子堆中取出 \(1\sim m\) 个石子。无法操作者输,问最后谁会获胜。
先手必败当且仅当 \(n\equiv 0\pmod {m+1}\)，可以归纳证明。
SG 函数及与其有关的游戏
公平组合游戏的 SG 函数
考虑 DAG \(E\) 上的移动游戏。定义
\[SG(u)=\operatorname{mex}\{SG(v)\mid (u,v)\in E\} \]容易发现节点 \(u\) 先手必败当且仅当 \(SG(u)=0\)。
SG定理
一个公平组合游戏可以被一个数，即 SG 函数等价（等价定义见下）。
证明：
首先定义一个游戏的位置（position）是当前局面可以转移到的局面的集合。
两个（可以认为是不同游戏平行进行）位置 \(S\) 和 \(S'\) 的和：\(S+S'=\{S+s'\mid s'\in S\}\cup \{s+S'\mid s\in S\}\)。这告诉我们，加法满足交换律和结合律。
定义两个位置 \(G,G'\) 等价： \(G\approx G'\) 当且仅当 \(\forall H,G+H,G'+H\) 在同一结果类中。这样的等价关系明显是传递的。
Lemma 1
\[\forall A\in \mathcal{P},G\approx G+A \]设 \(H\) 是任意位置。
证明：若 \(G+H\in\mathcal{P}\)，\(A+G+H\) 显然有后手获胜策略。
若 \(G+H\in\mathcal N\)，\(A+G+H\) 可以选择一个 \(G+H\) 的 \(\mathcal P\) 位置 \((G+H)'\)，之后 \(A+(G+H)'\in \mathcal P\)，根据上一行。所以 \(A+G+H\in \mathcal N\)。证毕。
Lemma 2
\(G\approx G'\iff G+G'\in \mathcal P\)。
证明：
先证 \(G\approx G'\Rightarrow G+G'\in \mathcal P\)。
根据定义，\(G'+G(=G+G')\) 和 \(G+G\) 在一个结果类。而显然 \(G+G\in \mathcal P\)，那么 \(G'+G\in \mathcal P\)。
再证 \(G\approx G'\Leftarrow G+G'\in \mathcal P\)。
设 \(A=G+G'\)，则 \(A\in \mathcal P\)。根据 Lemma 1,
\[G\approx G+A=G+(G+G')\\=(G+G)+G'=G'+(G+G)\approx G' \]那么 \(G\approx G'\)。
接下来证明原命题。
使用归纳证明之。
考虑位置 \(G=\{G_1,G_2,\dots, G_k\},G'=\{*n_1,*n_2,\dots,*n_k\}\)。
下面证明：\(G\approx *m=\operatorname{mex}(*n_i)\)。
先证明 \(G\approx G'\)。考虑 \(G+G'\)：由归纳假设这是 \(\mathcal P\)，后手可以通过 \(G,G'\) 中的另一个的与之等价的东西回复先手，而 \(A+A\in\mathcal P\)。所以 \(G+G'\in \mathcal P\)。
再证明 \(G'+*m\in\mathcal P\)，显然 \(G'+*m\in\mathcal P\Rightarrow G\approx *m\)。
构造此方案。
考虑先手在 \(*m\) 移动到 \(m'<*m\)，而后手可以把 \(G'\) 移动到 \(m'\) 得到两个相等的局面，因为 \(m\) 是 \(\operatorname{mex}\)。
如果先手在 \(G'\) 移动到 \(*n_i\)，若 \(*n_i<*m\)，后手把 \(*m\) 移到 \(*n_i\)；否则后手把这个 \(*n_i\) 搞成 \(*m\)。这样都会得到两个相等的局面。那么 \(G'+*m\in \mathcal P\)。
因此，\(SG\) 函数被证明和游戏等价。
Nim 和
看起来有很多人认为这是 SG 定理，尽管并非如此。
根据 SG 定理：我们已经知道一个公平组合游戏等价于一个 Nim 堆。
以下假设 \(\oplus\) 是异或。
设目前的 \(n\) 堆是 \(x_1,x_2,\dots,x_n\)，操作后变成 \(y_1,y_2,\dots,y_n\)，改变的是第 \(k\) 堆。
设 \(s=\oplus x_i,t=\oplus y_i\)，不难发现 \(t=s\oplus x_k\oplus y_k\)。
Lemma 1
若 \(s=0\)，\(\forall t,t\neq 0\)。如果没有移动，命题是 vacuously true。如果移动了，由于 \(y_k<x_k\)，命题是显然的。
Lemma 2
若 \(s\neq 0\)，\(\exists t,t=0\)。设 \(d\) 是 \(s\) 的最高的非零位，选择 \(k\) 使 \(x_k\) 的 \(d\) 非零。令 \(y_k=s\oplus x_k\)，此时 \(y_k<x_k\)。此时不难发现 \(t=0\)。
归纳可以证明 Nim 和。
P2197 代码：
#include<bits/stdc++.h>
using namespace std;
int T,n,a,ans;
int main(){
cin>>T;
while(T--){
cin>>n>>a;ans=a;
for(int i=1;i<n;i++)cin>>a,ans^=a;
if(ans)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}