learn more useless things.

0x01：从 Nim 游戏入手

P2197 【模板】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\)。

当然这是对于单局游戏来谈的，如果有多个起始状态怎么办呢？

AcWing 1319. 移棋子游戏

给定一个有 \(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;
}

其他例题：

AcWing 1321. 取石子

P2599 [ZJOI2009]取石子游戏

等等等等。