算法学习笔记（Nim游戏）

$Nim$游戏

$n$堆物品，每堆有$a_i$个，每个玩家轮流取走任意一堆的任意个物品，但不能不取，取走最后一个物品的人获胜。

$Nim$游戏是一种经典的公平组合游戏。现在对它进行分析。

首先定义两个博弈中的状态：

• 必胜状态：先手必胜的状态。
• 必败状态：先手必败的状态。

对于这两个状态，我们可以知道：

1. 没有后继状态的状态必然是必败状态。在这个状态中先手的是败者，因为他无法通过操作将游戏进行下去了。
2. 一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。在这个状态中先手的人可以通过一次操作让对手在必败状态中先手。
3. 一个状态的所有后继状态均为必胜状态，那么这个状态为必败状态。在这个状态中先手，无法避免让对方在必胜状态中先手。

回到$Nim$游戏：

在$Nim$游戏中，一个很显然的必败状态就是所有物品堆中物品的数量都为$0$，即$[0,0,...,0]$。这个状态也是最终态。可以知道，在最终态时，所有物品堆中的物品数量的异或和是等于$0$的，我们不妨假设状态和物品数量的异或和有关系。

证明有关：

一个非$0$的异或和，产生最高位的$1$总需要有奇数个数字来提供对应位置的$1$。而我们为了消去这个$1$，可以选择任意一个提供这个$1$的数字，使其二进制中该位上的数字为$0$,而且修改最高位为$0$后得到的数字永远小于原来的数字，也就是说，我们可以任意修改其他位上的数字从而使得全部物品数量的异或和为$0$。

而对于一个为$0$的异或和，假设存在一个$b\ne a_i$使得我们将$a_i$修改为$b$后，异或和还是为$0$，则有$0\oplus a_i\oplus b=0$，为了使这个式子成立$b$就要等于$a_i$，与假设违背。

换句话说，对于一个物品数量异或和不为$0$的状态，我们可以通过一次操作将物品数量的异或和修改为$0$，而对于一个物品数量异或和为$0$的操作，我们无法只通过一次操作保持物品数量的异或和不变。

从上可以得出，在$Nim$游戏中，物品数量异或和为$0$的状态是必败状态，物品数量异或和不为$0$的状态是必胜状态。

接下来看例题：

【模板】Nim 游戏

【模板】Nim 游戏

题目描述

甲，乙两个人玩 nim 取石子游戏。

nim 游戏的规则是这样的：地上有 $n$ 堆石子（每堆石子数量小于 $10^4$），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 $n$ 堆石子的数量，他想知道是否存在先手必胜的策略。

输入格式

本题有多组测试数据。

第一行一个整数 $T$ （$T\le 10$），表示有 $T$ 组数据

接下来每两行是一组数据，第一行一个整数 $n$，表示有 $n$ 堆石子，$n\le 10^4$。

第二行有 $n$ 个数，表示每一堆石子的数量.

输出格式

共 $T$ 行，每行表示如果对于这组数据存在先手必胜策略则输出 Yes，否则输出 No。

样例 #1

样例输入 #1

2
2
1 1
2
1 0

样例输出 #1

No
Yes

根据刚才的推论，我们只需要计算所有数字的异或和，就可以得出先手时处在必胜状态还是必败状态。用$O(n)$的复杂度即可得出最后的胜负结果。

#include<bits/stdc++.h>
using namespace std;

void solve()
{
    int n; cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; ++i)
    {
        int x; cin >> x;
        ans ^= x;
    }
    cout << (ans ? "Yes" : "No") << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _; cin >> _;
    while(_--) solve();
    return 0;
}