【博弈论 Nim问题】洛谷 P2197 【模板】Nim 游戏

题目

https://www.luogu.com.cn/problem/P2197

题解

经典 Nim 游戏是数学领域的公平组合数学博弈论问题，公平组合游戏具备以下特征：

1. 完全性（完全信息）
2. 确定性（无随机因素）
3. 相同性（双方操作集合相同）
4. 有穷性（有限步骤内结束）

核心理论

• 必败态（P-position）：当前局面下，轮到操作的一方无论如何走，都会将对手送入必胜态。即“谁走谁输”（假设对方的应对手段不出现失误）。
• 必胜态（N-position）：当前局面下，操作的一方存在一种走法，能将局面变为必败态送给对手。即“谁走谁赢”。

关键结论
对于一个 Nim 局面 \(a_1,a_2,...,a_n\)，计算所有数的二进制异或和：\(value\_xor=a_1 \text{^} a_2 \text{^} ... \text{^} a_n\)
若异或和 \(value\_xor == 0\)，则该局面为 必败态；
若异或和 \(value\_xor != 0\)，则该局面为 必胜态。

简单论证
从二进制入手，论述关键结论为什么成立：

若异或和 \(value\_xor != 0\)，那么必然存在一种取法，使得取完后异或和变为 \(0\)。
\(\because\) 异或运算具有结合性
\(\therefore a_1 \text{^} a_2 \text{^} ... \text{^} a_n = a_1 \text{^} (a_1 \text{^} x) = x\)
因此，只需要先手移走 \(x\) 颗，即可让对手进入必败态

不妨以 \(100_2, 010_2, 001_2\) 为案例进行分析
此时异或和为 \(100_2 \text{^} 010_2 \text{^} 001_2 = 111_2\)
因为异或和的最高非 \(0\) 位，必然出现于至少一个 \(a_i(1 \leq i \leq n)\) 中
那么只需要从最高非 \(0\) 位，取走 \(111_2 - (010_2 \text{^} 001_2) = 111_2 - 011_2 = 001_2\) 颗即可送对手进入必败态

随后再来分析为什么必败态是必败的：
\(\because\) 异或运算具有结合性
\(\therefore 当 value\_xor == 0 时，有 a_1 \text{^} a_2 \text{^} ... \text{^} a_n = x \text{^} x\)
那么易知：\(x \geq 0\) 成立

1)当 \(x == 0\) 时，后手者无石子可取，已败
2)当 \(x > 0\) 时
\(\because\) 每个人取走的石子数量 \(x'\) 必须是正数
即满足 \(x' > 0\)
此时满足：\(value\_xor \text{^} x' = 0 \text{^} x' = x' > 0\)
那么对手又会进入必胜态，相当于自身仍处于必败态

彼之失乃吾之得是一种广义的博弈论思想，意思是对方的失误或损失，自然就是我的所得。这个思想用于作为 Nim 游戏的指导思想很恰当，Nim 游戏有时候并不能直接通过选择让自己胜利，但是可以通过让对方陷入不利的局面（有可能直接是必败态）来达成目的，对方失败就是自己胜利。

参考代码

#include<iostream>

int main() {
    std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
    int T, n, m, a;
    std::cin >> T;
    while (T --) {
        std::cin >> n;
        m = 0;
        for (int i = 0; i < n; ++ i) {
            std::cin >> a;
            m ^= a;// 求异或
        }
        std::cout << (m ? "Yes\n" : "No\n");// 0为必败态，否则为必胜态
    }
    return 0;
}