# 博弈论

博弈论，又称为对策论（Game Theory）、赛局理论等，既是现代数学的一个新分支，也是运筹学的一个重要学科。
博弈论主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。 -- 百度百科

# 公平组合游戏

公平组合游戏是博弈论的一种类型。它是一种特殊的棋类游戏，必须满足三点规则：

1. 两名玩家交替行动；
2. 游戏进行的任意时刻，可以进行的合法行动，与轮到哪名玩家无关；
3. 不能行动的玩家判负；

其中规则 1 和 3 都比较好理解，而第二点表达的含义是在该规则内每个玩家所能做的操作完完全全相同，比如在象棋中，红方只能动红色的棋子，而黑方只能动黑色的棋子，则违反了这条规则。

# Nim 游戏

给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

# 结论

通过题目可以发现，尼姆游戏就是一种公平组合游戏。而针对该题目，其实早就有了标准的结论：假设 n 堆石子，每堆石子的数目是 ai 个，那么如果 a1^a2^a3^...^an!=0 则先手必胜，否则必败。

# 如何算是先手必胜呢？

注意这种问题的一个重要条件，既双方都采用最优策略。这是先手必胜的基础。

假设当前有两堆石子，一堆有 2 个，一堆有 3 个，只要按照如下两步操作，就可以做到先手必胜：

1. 先手从 3 个的那堆，拿走一个。此时，两堆的数量相同，都是两个石子。
2. 轮到后手行动，无论这次后手怎么做，下次先手都做相同的操作，即可必胜。

举这个例子，其实是为了引出两个重要的概念（或者叫状态）：

1. 先手必胜状态：当前轮到先手操作，那么当前做的 任意一个 操作，可以给下一步操作的后手留下先手必败状态，则称为先手必胜状态。
2. 先手必败状态：当前轮到先手操作，那么当前能做的 全部 操作，均会给后手留下先手必胜状态，则称为先手必败状态。

# 结论的证明

异或的运算规则是：二进制位，相同为 0，不同为 1。其符号用$\oplus$ 表示。

1. 可以预见的结论是：到分胜负的时候，一定是所有的石子都被拿完，也就是每个石子都是 0，那么一定有：$a_1=0,a_2=0,a_3=0,....,a_n=0$。把他们全部 异或 起来，一定是：${a_1}\oplus {a_2} \oplus ... \oplus a_n=0$。

2. 在游戏的过程中，如果${a_1}\oplus {a_2} \oplus ... \oplus a_n=x \ne 0$ ，那么，我们一定可以通过修改其中的一个$a_i$ ，让等式成立。

   证明：

   1. 假设，x 由高位到低位的第一个 1，出现在第 k 位，那么 a1~an 中一定至少有一个 1 ，这是因为，如果 a1~an 所有数的第 k 位都是 0，那么这些数异或起来的第 k 位一定也是 0。我们用$a_i$ 来表示这个数。

   2. 显然，$a_i \oplus x < a_i$ 是一定成立的。因为他们俩的第 k 位都是 1，所以异或后$a_i$ 的第 k 位变成 0，而比 k 更高的位则不变，所以$a_i$ 整体是变小的。

   3. 所以，我们就可以从$a_i$ 当中拿走 $a_i - (a_i \oplus x) $个石子（注意刚才已经说明了$ a_i \oplus x < a_i$， 所以该操作合法）。那么剩下的石子就是$ a_i - (a_i - (a_i \oplus x))=a_i \oplus x$ 。

   4. 所以，本次操作之后剩余的石子数变成了$a_1\oplus a_2 \oplus a_3\oplus ... \oplus a_i \oplus x \oplus ... \oplus a_n$ 。

   5. 而在最开始，我们已经知道了${a_1}\oplus {a_2} \oplus ... \oplus a_n=x$，所以上一步的公式又可以转换为$x \oplus x = 0$。

   6. 所以，我们就证明出了可以通过拿走$a_i - (a_i \oplus x)$ 个数字让等式${a_1}\oplus {a_2} \oplus ... \oplus a_n=0$ 成立。

3. 轮到后手行动的时候，无论怎么选都会破坏上面的等式。

   证明：

   1. 使用反证法，假设第二个人从第 i 堆拿走了若干石子，可以使公式仍然成立。用 $a_i ^ \prime $ 表示第 i 堆剩余的数量，那么根据题目中的条件可以全拿走，但是不能不拿，我们可以知道 $0 \le a_i ^ \prime < a_i $ (记住这个 结论 ，下一步要用)。

   2. 而我们假设的是，本次拿完石子后仍然有${a_1}\oplus {a_2} \oplus ... \oplus a_n=0$ （记为公式 1）。所以，通过第一步，就可以得到：${a_1}\oplus {a_2} \oplus ... \oplus{a_i^\prime } \oplus... \oplus a_n=0$ （记为公式 2）。将两个公式联立起来，可以得到：${(公式1)} \oplus {(公式2)} = 0$ ，而两个公式除了$a_i和a_i^ \prime$ 之外，没有任何不同，所以我们可以得到$a_i \oplus a_i^\prime = 0$ ，也就是说 $a_i = a_i^\prime$ ，而此公式和步骤 1 中的 结论 冲突。

4. 综合步骤 2 和 3，我们就可以得到最开始的结论，既：如果开局 $a_1 \oplus a_2\oplus a_3 \oplus ... \oplus a_n!=0$ ，那么先手必然可以通过拿走某堆的若干个石子让等式成立，而后手一定又会将等式破坏，先手又将等式还原，后手破坏，如此反复，直到等式最后一次成立，也就是 a1~an 全部为 0，后手失败。

# Code

输入样例：
2
2 3
输出样例：
Yes

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 100010;

int nums[N];

int main () {

    int n;

    cin >> n;

    int res = 0;

    for (int i = 0; i < n; i ++ ) {

        cin >> nums[i];

        res ^= nums[i];

    }

    if (res) puts("Yes");

    else puts("No");

    return 0;

}