AcWing 891. Nim 游戏

◎

本节目标

用总异或和判断普通 Nim 的必胜态与必败态。

查看原题

返回博弈与计算几何框架

题意与约束

有若干石子堆，双方轮流从任意一堆取走至少一个石子，无法行动者输。判断先手是否必胜。

第一反应与瓶颈

枚举每次从哪一堆取多少，会形成指数级博弈树。普通 Nim 的胜负并不取决于总石子数，而是存在一个可一次汇总的不变量。

数学关系与算法推导

令所有堆大小的异或和为 xorSum。xorSum = 0 时，无论先手怎样改变一堆，都会得到非零异或和；xorSum ≠ 0 时，先手能选一堆把它改成更小值，使新异或和为零。

正确性依据

零异或和无法一步仍保持零，因此只能交给对手非零态。非零异或和最高为 1 的位所在的某堆可被降低到目标值，使异或归零。双方重复这一配对关系，零态是必败、非零态是必胜。

样例执行过程

堆 [2, 3] 的异或为 1，先手可把 3 变为 2，留下 [2, 2] 的零异或和。[1, 2, 3] 的异或本来为零，所以是必败态。

代码实现

C++

C++17

#include <iostream>
#include <vector>
using namespace std;

bool firstPlayerWins(const vector<int>& piles) {
    int xorSum = 0;
    for (int pile : piles) {
        xorSum ^= pile;
    }
    return xorSum != 0;
}

int main() {
    int n;
    cin >> n;
    vector<int> piles(n);
    for (int i = 0; i < n; i++) {
        cin >> piles[i];
    }
    cout << (firstPlayerWins(piles) ? "Yes" : "No") << '\n';
    return 0;
}

Python

Python 3

import sys


def first_player_wins(piles: list[int]) -> bool:
    xor_sum = 0
    for pile in piles:
        xor_sum ^= pile
    return xor_sum != 0


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    print('Yes' if first_player_wins(data[1:]) else 'No')


if __name__ == '__main__':
    main()

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)，不计输入数组。

边界与易错点

• 单堆正石子时异或非零，先手获胜。
• 判断的是按位 XOR，不是和、奇偶性或最大堆大小。
• 结论只对应本题普通 Nim 规则，不自动推广到取法受限的变体。

模式迁移

遇到轮流操作的题，先寻找能把状态分为必胜／必败两类的不变量。本题止于 Nim 的异或模型，不扩展到 SG 函数。