题目描述
这是 LeetCode 上的 810. 黑板异或游戏 ，难度为 困难。
Tag : 「博弈论」、「数学」、「异或」
黑板上写着一个非负整数数组 nums[i] 。
Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 (另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。）
换种说法就是，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0，这个玩家获胜。
假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。
示例：
输入: nums = [1, 1, 2] 输出: false 解释: Alice 有两个选择: 擦掉数字 1 或 2。 如果擦掉 1, 数组变成 [1, 2]。剩余数字按位异或得到 1 XOR 2 = 3。那么 Bob 可以擦掉任意数字，因为 Alice 会成为擦掉最后一个数字的人，她总是会输。 如果 Alice 擦掉 2，那么数组变成[1, 1]。剩余数字按位异或得到 1 XOR 1 = 0。Alice 仍然会输掉游戏。 复制代码
提示：
- 1 <= N <= 1000
- 0 <= nums[i] <= 2162^{16}216
基本分析
这是一道「博弈论」题。
如果没接触过博弈论，其实很难想到，特别是数据范围为 10310^3103，很具有迷惑性。
如果接触过博弈论，对于这种「判断先手后手的必胜必败」的题目，博弈论方向是一个优先考虑的方向。
根据题意，如果某位玩家在操作前所有数值异或和为 000，那么该玩家胜利。要我们判断给定序列时，先手是处于「必胜态」还是「必败态」，如果处于「必胜态」返回 True，否则返回 False。
对于博弈论的题目，通常有两类的思考方式：
- 经验分析：见过类似的题目，猜一个性质，然后去证明该性质是否可推广。
- 状态分析：根据题目给定的规则是判断「胜利」还是「失败」来决定优先分析「必胜态」还是「必败态」时具有何种性质，然后证明性质是否可推广。
博弈论
对于本题，给定的是判断「胜利」的规则（在给定序列的情况下，如果所有数值异或和为 000 可立即判断胜利，其他情况无法立即判断胜负），那么我们应该优先判断何为「先手必胜态」，如果不好分析，才考虑分析后手的「必败态」。
接下来是分情况讨论：
1. 如果给定的序列异或和为 000，游戏开始时，先手直接获胜：
由此推导出性质一：给定序列 nums 的异或和为 000，先手处于「必胜态」，返回 True。
2. 如果给定序列异或和不为 000，我们需要分析，先手获胜的话，序列会满足何种性质：
显然如果要先手获胜，则需要满足「先手去掉一个数，剩余数值异或和必然不为 000；同时后手去掉一个数后，剩余数值异或和必然为 000」。
换句话说，我们需要分析什么情况下「经过一次后手操作」后，序列会以上述情况 111 的状态，回到先手的局面。
也就是反过来分析想要出现「后手必败态」，序列会有何种性质。
假设后手操作前的异或和为 SumSumSum（Sum≠0Sum \neq 0Sum=0），「后手必败态」意味着去掉任意数字后异或和为 000。
同时根据「相同数值异或结果为 000」的特性，我们知道去掉某个数值，等价于在原有异或和的基础上异或上这个值。
则有：
Sum′=Sum⊕nums[i]=0Sum' = Sum ⊕ nums[i] = 0Sum′=Sum⊕nums[i]=0
由于是「后手必败态」，因此 iii 取任意一位，都满足上述式子。
则有：
Sum⊕nums[0]=...=Sum⊕nums[k]=...=Sum⊕nums[n−1]=0Sum ⊕ nums[0] = ... = Sum ⊕ nums[k] = ... = Sum ⊕ nums[n - 1] = 0Sum⊕nums[0]=...=Sum⊕nums[k]=...=Sum⊕nums[n−1]=0
同时根据「任意数值与 000 异或数值不变」的特性，我们将每一项进行异或：
(Sum⊕nums[0])⊕...⊕(Sum⊕nums[k])⊕...⊕(Sum⊕nums[n−1])=0(Sum ⊕ nums[0]) ⊕ ... ⊕ (Sum ⊕ nums[k]) ⊕ ... ⊕ (Sum ⊕ nums[n - 1]) = 0(Sum⊕nums[0])⊕...⊕(Sum⊕nums[k])⊕...⊕(Sum⊕nums[n−1])=0
根据交换律进行变换：
(Sum⊕Sum⊕...⊕Sum)⊕(nums[0]⊕...⊕nums[k]⊕...⊕nums[n−1])=0(Sum ⊕ Sum ⊕ ... ⊕ Sum) ⊕ (nums[0] ⊕ ... ⊕ nums[k] ⊕ ... ⊕ nums[n - 1]) = 0 (Sum⊕Sum⊕...⊕Sum)⊕(nums[0]⊕...⊕nums[k]⊕...⊕nums[n−1])=0
再结合 SumSumSum 为原序列的异或和可得：
(Sum⊕Sum⊕...⊕Sum)⊕Sum=0,Sum≠0(Sum ⊕ Sum ⊕ ... ⊕ Sum) ⊕ Sum = 0 , Sum \neq 0(Sum⊕Sum⊕...⊕Sum)⊕Sum=0,Sum=0
至此，我们分析出当处于「后手必败态」时，去掉任意一个数值会满足上述式子。
根据「相同数值偶数次异或结果为 000」的特性，可推导出「后手必败态」会导致交回到先手的序列个数为偶数，由此推导后手操作前序列个数为奇数，后手操作前一个回合为偶数。
由此推导出性质二：只需要保证先手操作前序列个数为偶数时就会出现「后手必败态」，从而确保「先手必胜态」。
代码：
class Solution { public boolean xorGame(int[] nums) { int sum = 0; for (int i : nums) sum ^= i; return sum == 0 || nums.length % 2 == 0; } } 复制代码
- 时间复杂度：O(n)O(n)O(n)
- 空间复杂度：O(1)O(1)O(1)
总结
事实上，在做题的时候，我也是采取「先假定奇偶性，再证明」的做法，因为这样比较快。
但「假定奇偶性」这一步是比较具有跳跃性的，这有点像我前面说到的「经验分析解法」，而本题解证明没有做任何的前置假定，单纯从「先手必胜态」和「后手必败态」进行推导，最终推导出「先手序列偶数必胜」的性质 ，更符合前面说到的「状态分析解法」。
两种做法殊途同归，在某些博弈论问题上，「经验分析解法」可以通过「归纳」&「反证」很好分析出来，但这要求选手本身具有一定的博弈论基础；而「状态分析解法」则对选手的题量要求低些，逻辑推理能力高些。
两种方法并无优劣之分，都是科学严谨的做法。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.810 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
