learn more useless things.
0x01：从 Nim 游戏入手
甲，乙两个人玩 Nim 取石子游戏。
Nim 游戏的规则是这样的：地上有 \(n\) 堆石子，每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。给你一个局面，问先手是否必胜。
首先给出一个结论，设每堆石子的个数为 \(a_i\)，则先手必胜的充要条件是
其中 \(\oplus\) 表示异或运算，考虑证明：
-
首先对于结束的局面，显然异或和都为 \(0\)（啥都没有了）。
-
设 \(a_1\oplus a_2\oplus … \oplus a_n=k\)，对于 \(k\) 的二进制最高位 \(i\)，我们一定能从这 \(n\) 堆石子里找到一堆石子满足其最高位也为 \(i\)。假设是 \(a_j\)，则我们令 \(a_j\leftarrow a_j\oplus k\)，此时 \(a_j\) 一定变小（即能取得到石子）。这时整个局面异或和为 \(0\)，后手无论怎么取都会改变异或值。那么显然先手会先到达结束局面，从而先手必胜。
好了，这样你就可以做这道题了。
0x02：SG 函数
首先我们要明确一个事实，博弈游戏状态间一定形成一个 DAG，即不存在撤销操作和环（不然就结束不了了），like this：
首先我们来确认一下什么样的状态先手必胜、先手必败。
显然，没有出度的节点为先手必败（啥状态都走不到），如节点 \(4、5\)。
其次，若从一个节点到达的所有节点都是必胜节点，则其先手必败，如节点 \(2\)。
反之，若从一个节点到达的节点存在必败节点，则其先手必胜，如节点 \(0\)。
这样，我们可以引入一个概念：SG 函数。它的定义是这样的：
-
对于没有出度的状态 \(S_u\)， \(SG(S_u)=0\)。
-
对于出度不为 \(0\) 的状态 \(S_u\)，其 SG 函数定义为其所有到达节点的 SG 函数的 \(\operatorname{mex}\)（最小的不存在的自然数），即 \(SG(S_u)=\operatorname{mex}_{v\in to(u)}SG(S_v)\)。
我们可以对上图标注出对应 SG 函数的值：
容易发现，对于先手必胜局面 \(S_u\)，有 \(SG(S_u)\not=0\)，对于先手必败局面，有 \(SG(S_u)=0\)。
当然这是对于单局游戏来谈的，如果有多个起始状态怎么办呢？
给定一个有 \(N\) 个节点的有向无环图，图中某些节点上有棋子，两名玩家交替移动棋子。
玩家每一步可将任意一颗棋子沿一条有向边移动到另一个点，无法移动者输掉游戏。
对于给定的图和棋子初始位置，双方都会采取最优的行动，询问先手必胜还是先手必败。
我们发现玩家每次操作可以移动不同的棋子，那如何判断先手必胜还是必败呢？
结论，设每个棋子的起始状态为 \(S_i\)，则先手必胜的充要条件是
是不是似曾相识？对！是 Nim 游戏！
类似 Nim 游戏的证明方法，我们再来证明一下：
-
首先对于结束状态，所有棋子的出度为 \(0\)，显然 SG 函数都为 \(0\)，故异或和也为 \(0\)。
-
设 \(SG(S_1)\oplus SG(S_2)\oplus … \oplus SG(S_k) = k\)，则对于 \(k\) 的最高位 \(i\) 我们一定能找到一个 \(S_j\)，满足 \(SG(S_j)\) 的最高位也为 \(i\)，令 \(SG(S_j)\leftarrow SG(S_j)\oplus k\)，从而使得异或和为 \(0\)。而后手无论怎么移动，都会使异或和不为 \(0\)。
诶诶诶等一下，怎么证明存在 \(S_j\) 到达的局面 \(S_v\) 使得 \(SG(S_v)=SG(S_j)\oplus k\) 啊？
还记得 SG 函数的定义嘛？
- 对于出度不为 \(0\) 的状态 \(S_u\)，其 SG 函数定义为其所有到达节点的 SG 函数的 \(\operatorname{mex}\)（最小的不存在的自然数），即 \(SG(S_u)=\operatorname{mex}_{v\in to(u)}SG(S_v)\)。
既然是 \(\operatorname{mex}\)，则其到达的所有节点一定存在 \(SG(S_v)\in [0,SG(S_u))\)。且对于选中的 \(S_j\)， $SG(S_j)\leftarrow SG(S_j)\oplus k $ 一定会变小，故一定有满足条件的局面可以到达。
如何求 SG 函数？答案是暴力（
考虑用个 \(set\) 存所有到达节点的 SG 函数值，然后暴力枚举找最小且没出现过的值即可。
看起来很暴力，事实上用记忆化，对于 \(n\) 点 \(m\) 边的 DAG，到达节点的总数只有 \(m\) 个（包括重复），用 \(set\) 插入+查询的复杂度总共就 \(O(m\log m)\)，于是求所有点的 SG 函数的复杂度只有 \(O(n+m\log m)\)。代码如下：
int SG(int u){
if(sg[u]!=-1)return sg[u];
set<int>st;
for(int v:e[u])st.insert(SG(v));
for(int i=0;;++i)if(!st.count(i)){sg[u]=i;break;}
return sg[u];
}
事实上大部分题都不会利用到 SG 函数（吧），应用的只是判断必胜和必败的定义，可以写出下面的记忆化：
bool dfs(int u){
if(vis[u])return f[u];
vis[u]=1;bool ok=0;
for(int v:e[u]){
ok|=!dfs(v);//可以根据必胜必败的定义思考一下
}
return f[u]=ok;
}
0x03：分析方法
一般做题的思路有：
- 明确必胜态与必败态的关系，注意特殊条件。
- 考虑结束局面（先手必败）或结束前一个局面（先手必胜），根据操作猜性质。
- 考虑操作对局面有什么影响，最大/小操作数是多少？
- 若操作有一定的规则（如一段序列只能从左右取石子（说的就是 P2599）），可以考虑当前局面下一步怎么做能使得先手必败。（一般有一堆分讨）
- 待补充
0x04：2022/10/17 补充例题：
G. Game on Sequence
考虑分析这道题：
- 注意特殊条件
只能跳到后面值的二进制位最多 1 位与自己不同的地方，也就是说还可以跳到与自己值相等的地方！注意到若当前的后面还有与自己相等的值，那么当前一定是必胜的，可以分类讨论：
若后面的位置是必败的，显然当前必胜（直接走）；若后面是必胜的，显然当前可以学他走（毕竟值相等），也是必胜的。
也就是说对于一个值我们只用关心它最后一次出现的位置，题中 \(0\le A_i\le255\)，也就是说实际要管的位置很少。对于每次查询直接记忆化就好了。
点击查看代码
#define pb push_back
#define mp make_pair
const int N=4e5+10,M=300;
int n,m;
int a[N],lst[M];
bool vis[M],f[M];
vector<int>to[M];
void init(){
for(int i=0;i<=255;++i){
lst[i]=-1;
for(int j=0;j<8;++j){
to[i].pb(i^(1<<j));
}
}
}
bool dfs(int cur){
if(vis[a[cur]])return f[a[cur]];
vis[a[cur]]=1;bool ok=0;
for(int v:to[a[cur]]){
if(lst[v]<cur)continue;
ok|=!dfs(lst[v]);
}
return f[a[cur]]=ok;
}
int main(){
read(n),read(m);init();
for(int i=1;i<=n;++i)read(a[i]),lst[a[i]]=i;
for(int i=1,op,k;i<=m;++i){
read(op),read(k);
if(op==1){
a[++n]=k;lst[k]=n;
}else {
memset(vis,0,sizeof vis),memset(f,0,sizeof f);
if(lst[a[k]]!=k)printf("Grammy\n");
else dfs(k)?printf("Grammy\n"):printf("Alice\n");
}
}
return 0;
}
其他例题：
等等等等。
原文地址：http://www.cnblogs.com/RuntimeErr/p/16759661.html
