810.黑板异或游戏

题目描述：

解：

学自【宫水三叶の相信科学系列】应用「博弈论」分析「先手必胜态」序列具有何种性质

基本分析
这是一道「博弈论」题。
如果没接触过博弈论，其实很难想到，特别是数据范围为 10^3，很具有迷惑性。
如果接触过博弈论，对于这种「判断先手后手的必胜必败」的题目，博弈论方向是一个优先考虑的方向。

根据题意，如果某位玩家在操作前所有数值异或和为 0，那么该玩家胜利。要我们判断给定序列时，先手是处于「必胜态」还是「必败态」，如果处于「必胜态」返回 True ，否则返回 False
对于博弈论的题目，通常有两类的思考方式：
经验分析：见过类似的题目，猜一个性质，然后去证明该性质是否可推广。
状态分析：根据题目给定的规则是判断「胜利」还是「失败」来决定优先分析「必胜态」还是「必败态」时具有何种性质，然后证明性质是否可推广。

博弈论
对于本题，给定的是判断「胜利」的规则（在给定序列的情况下，如果所有数值异或和为 0 可立即判断胜利，其他情况无法立即判断胜负），那么我们应该优先判断何为「先手必胜态」，如果不好分析，才考虑分析后手的「必败态」。

接下来是分情况讨论：

如果给定的序列异或和为 0，游戏开始时，先手直接获胜：
由此推导出性质一：给定序列 nums 的异或和为 0，先手处于「必胜态」，返回 True。
如果给定序列异或和不为 0，我们需要分析，先手获胜的话，序列会满足何种性质：
显然如果要先手获胜，则需要满足「先手去掉一个数，剩余数值异或和必然不为 0；同时后手去掉一个数后，剩余数值异或和必然为 0」。换句话说，我们需要分析什么情况下「经过一次后手操作」后，序列会以上述情况 11 的状态，回到先手的局面。也就是反过来分析想要出现「后手必败态」，序列会有何种性质。
根据「相同数值偶数次异或结果为 0」的特性，可推导出「后手必败态」会导致交回到先手的序列个数为偶数，由此推导后手操作前序列个数为奇数，后手操作前一个回合先手为偶数。
由此推导出性质二：只需要保证先手操作前序列个数为偶数时就会出现「后手必败态」，从而确保先手必胜。

综上，如果序列 nums 本身异或和为 0，天然符合「先手必胜态」的条件，答案返回 True ；如果序列 nums 异或和不为 0，但序列长度为偶数，那么最终会出现「后手必败态」，推导出先手必胜，答案返回 True。

class Solution {
    public boolean xorGame(int[] nums) {
        int sum = 0;
        for (int i : nums) sum ^= i;
        return sum == 0 || nums.length % 2 == 0;
    }
}