博弈论—Nim游戏

题目描述

给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

原型

公平组合游戏ICG
若一个游戏满足:

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

则称该游戏为一个公平组合游戏。
NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

先手必胜状态：可以走到某一个必败状态
先手必败状态：走不到任何一个必败状态

结论

设n堆石子的个数为\(a_1, a_2...a_n\)，则

证明

我们将上述结论转换为证明下面三个结论：

1. 显然成立
2. 设x的二进制表示中，最高一位1在第k位，则由反证法知，\(a_1 - a_n\)中必定存在一个\(a_i\)，使得\(a_i 的第k位也是1\)，进而有\(a_i \oplus x < a_i\)，因此对第\(i\)堆石头，我们可以拿走\(ai - ai \oplus x\)个，使其变成\(a_i \oplus x\)个，此时\(a_1\oplus a_2\oplus ...\oplus ai \oplus x \oplus ...\oplus a_n = x \oplus x = 0\)，故原命题的证。
3. 应用反证法，对\(a_1\oplus a_2\oplus ...\oplus ai \oplus x \oplus ...\oplus a_n = 0\)，假设存在一种变换，使得\(a_1\oplus a_2\oplus ...\oplus ai' \oplus x \oplus ...\oplus a_n = x \neq 0\)，对两个等式左右两端分别取异或，可得\(a_i \oplus a_i' = 1\)，这说明\(a_i = a_i'\)，与我们初始条件矛盾，故原命题成立

从上述三个结论推出最终结论

若初始时\(a_1\oplus a_2\oplus...\oplus a_n = x\neq 0\)，则对先手来说，由结论2，他总能将当前的总异或值转换为0，而由结论3，后手面对总异或值为0的情况只能将其转换为1，如此反复，先手永远不是0，后手永远是0，显然这个游戏最终会停止，后手一定先遇到\(0 \oplus 0 \oplus ...\oplus 0 = 0\)的情况，即后手必输，先手必赢。

反之同理。

故原结论成立。

代码

#include<iostream>
using namespace std;
int main(void){
    int n;
    cin >> n;
    int ans = 0;
    while(n -- ){
        int x;
        cin >> x;
        ans ^= x;
    }
    if (ans) puts("Yes");
    else puts("No");
    return 0;
}