Nim游戏

Nim游戏属于公平组合游戏ICG，即满足以下特点：

  • 由两名玩家交替行动
  • 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关
  • 不能行动的玩家判负

先看一下模板题题目：

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

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

举个例子，对于两堆石子2 3，先手从第二堆拿了一个，变成2 2，那么接下来不管后手从哪一堆石子拿几个，先手只需要在另一堆石子里拿相同个数的石子就能保证最后后手没有石子取。比如后手从第一堆里拿一个，变成1 2，先手只需要在第二堆里拿一个，变成1 1，后手再从第一堆里拿一个，变成0 1，先手拿掉，变成0 0，先手获胜

我们先引出两个概念：

  • 先手必败状态：在Nim游戏中指先手遇到0 0，此时先手必败
  • 先手必胜状态：先手如果通过某些操作能够走到必败状态，即0 0，那么对手必败，即先手必胜

一般的，对于Nim游戏，我们有如下结论：对于每堆石子的个数a1，a2，a3，a4，…，an，如果满足a1⊕a2⊕a3⊕…⊕an=0a1\oplus a2\oplus a3\oplus …\oplus an = 0，那么先手必败，否则先手必胜

下给出证明：

如果异或值为0是先手必败状态，那么由上面的概念可以知道，异或值为x（x≠0）是先手必胜状态，此状态可以通过某些操作变成必败状态，即异或值为x（x≠0）一定能够转变成异或值为0，我们只需要证明这个

设x的二进制表示中最高一位1在第k位，那么由异或的概念，a1-an中必然存在一个数ai，ai的第k位是1

显然ai⊕x<aiai\oplus x < ai，原因是x的最高位1在第k位，ai的第k位也是1，两者异或为0，结果肯定小于ai

那么我们从ai中拿出ai−(ai⊕x)ai-(ai\oplus x)个石子（由前面的ai⊕x<aiai\oplus x < ai）易知其合法性，最后剩下ai⊕xai\oplus x个石子

拿走之后我们的异或值就变为0了，到了必败条件，得证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int res = 0;
    while(n--)
    {
        int t;
        cin >> t;
        res^=t;
    }
    if(res == 0) cout << "No";
    else cout << "Yes";
    return 0;
}