经典NIM游戏/取石子游戏

作为博弈论第一课来看一个非常经典有趣的问题——NIM游戏

NIM游戏属于博弈论中的ICG问题（公平组合游戏）

ICG问题需要满足下面三点

1. 由两名玩家交替移动
2. 在游戏进程的任意时刻可以执行的操作和轮到哪名玩家无关
3. 不能行动的玩家判负

需要注意的是，我们熟知的棋类游戏不属于ICG游戏，比如围棋双方下的棋子颜色不同

NIM游戏属于ICG游戏的典例

对于NIM游戏，有如下优美简洁的结论：

NIM游戏先手必胜，当且仅当

a_1 \oplus a_2 \oplus ...\oplus a_n \ne 0

下面给出简要的证明

要证上述结论，我们需要证明以下几点

1. 当所有石子异或和不为0时，我们可以通过一次合法操作令其异或和为0
2. 当所有石子异或和为0时，先手无论如何取，都不能令其异或和保持0
3. 当所有石子被取完时，先手必败（显然成立）

对第一点的证明：

当所有石子异或和不为0时，我们可以通过一次合法操作令其异或和为0

假设

x = a_1 \oplus a_2 \oplus ...\oplus a_n \ne 0

我们关注x二进制位最高的1，设为第k位，有如下结论：对于所有的ai，至少有一个二进制下第k位是1

因为由异或的性质可知如果 a xor b = 1，则ab必有一个1

我们可以做出一次合法操作令上述二进制第k位为1的a_i转变为a_i xor x

此时前后状态改变为

x = a_1 \oplus a_2 \oplus ...\oplus a_k \oplus ...\oplus a_n \ne 0 \\
x' = a_1 \oplus a_2 \oplus ...\oplus a_k \oplus x \oplus ...\oplus a_n = x \oplus x=0

而为什么这一次操作是合法的呢？ 观察二进制下ai xor x 的过程可以发现 因为x在第k位前都是0，所以a_i\’在第k位前保留了ai对应位置的部分

而第k位已经证明二者都是1，xor结果是0，所以后面的数字不用再关心(图中写问号的位置是0或者1都与结果无关)，因为a_i\’一定比a_i要小也就是我们一定可以取走ai的一部分石子，令a_i变为a_i\'(ai xor x)，此时所有石子的异或和(x)为0

现在证明第二点：

当所有石子异或和为0时，先手无论如何取，都不能令其异或和保持0

我们可以用反证法： 假设现在有a1~an其异或和为0，我们可以通过一次对ai的操作，令操作后的石子异或和仍未0 即

x = a_1 \oplus a_2 \oplus ...\oplus a_i \oplus ...\oplus a_n = 0 \\
x' = a_1 \oplus a_2 \oplus ...\oplus a_i' \oplus ...\oplus a_n = 0

将等式两边分别异或,成对的数值消去，可得

a_i \oplus a_i' = 0 \oplus 0 = 0

即

a_i = a_i'

与假设矛盾，故假设不成立

---

---

至此我们已经证明了该结论的正确性

现在来正向过一遍NIM游戏的思路吧

1. NIM游戏当且仅当所有石子异或和不为0时先手必胜
2. 这是因为我们先手要做出一次操作令其异或和为0，而对手无论如何操作都不能使异或和保持为0
3. 这会使得游戏像所有石子堆都为0的方向收束并最终胜利
4. 我们做出的操作是取出当且不为零的异或和x的二进制最高位1，记为第k位，然后找出一个二进制第k位同为1的a_i，令他变为a_i xor x
5. a_i xor x 一定会比a_i小，所以这次操作是合法的

上代码

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

int main()
{
    int res = 0;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        res ^= x;
    }
    if(res)
        puts("Yes");
    else
        puts("No");
    return 0;
}