题目描述

一个黑板上写着一个非负整数数组 nums[i]。小红和小明轮流从黑板上擦掉一个数字，小红先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。（另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。）

换种说法就是，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0，这个玩家获胜。

假设两个玩家每步都使用最优解，当且仅当小红获胜时返回 true。

样例

输入：nums = [1, 1, 2]
输出：false
解释：
小红有两个选择：擦掉数字 1 或 2。
如果擦掉 1，数组变成 [1, 2]。剩余数字按位异或得到 1 XOR 2 = 3。
那么小明可以擦掉任意数字，因为小红会成为擦掉最后一个数字的人，她总是会输。
如果小红擦掉 2，那么数组变成 [1, 1]。剩余数字按位异或得到 1 XOR 1 = 0。小红仍然会输掉游戏。

限制

• 1 <= N <= 1000
• 0 <= nums[i] <= 2^16

算法

(博弈论) $O(n)$

1. 如果所有数字异或和为 0，则显然先手获胜。
2. 否则，如果数组长度为偶数，则先手必胜；数组长度为奇数，先手必败。

证明

1. 令数组为 $a_1, a_2, \dots, a_n$，且 $a_1 \bigoplus a_2 \bigoplus \dots \bigoplus a_n = S$。现在假设 $S \neq 0$。
2. 此时先手需要去掉一个数字。如果先手去掉任意一个数字 $x$，都会导致 $S \bigoplus x = 0$，则先手才会必败，即对于任意的 $1 \le i \le n$，都有 $S \bigoplus a_i = 0$，先手必败。
3. 假设 $n$ 是偶数且先手必败，则将这些异或操作组合在一起，得到 $0 = (S \bigoplus a_1) \bigoplus (S \bigoplus a_2) \bigoplus \dots \bigoplus (S \bigoplus a_n) = S$，矛盾。所以 $n$ 为偶数时，存在 $a_k$，使得去掉 $a_k$ 后的异或和不为 0。
4. 当 $n$ 为奇数时，如果 $S$ 异或任何一个数字都等于 0，则先手必败；否则，先手无论选择哪个数字，局面都会变成后手面对偶数个异或和非零的数字。而刚才分析偶数的情况不会导致必败，所以到最后先手会面对只剩一个数字的情况，此时先手仍然必败。
5. 根据以上分析，$n$ 在偶数时，先手可以取一个数字让后手面对奇数个异或和非零的数字，此时后手必败，先手必胜。

时间复杂度

• 遍历一次数组，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool xorGame(vector<int>& nums) {
        int tot = 0;
        for (int x : nums)
            tot ^= x;

        if (tot == 0)
            return true;

        return nums.size() % 2 == 0;
    }
};