博弈论：台阶-Nim游戏

现在，有一个 nn 级台阶的楼梯，每级台阶上都有若干个石子，其中第i 级台阶上有 ai 个石子(i≥1)。

两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。

已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。

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

输入格式

第一行包含整数n。

第二行包含 n 个整数，其中第 i 个整数表示第 i 级台阶上的石子数 ai。

输出格式

如果先手方必胜，则输出 Yes。

否则，输出 No。

数据范围

11≤n≤10^5,
1≤ai≤10^9

输入样例：

3
2 1 3

输出样例：

yes

# 分析

此时我们需要将奇数台阶看做一个经典的Nim游戏，如果先手时奇数台阶上的值的异或值为0，则先手必败，反之必胜

证明：
先手时，如果奇数台阶异或非0，根据经典Nim游戏，先手总有一种方式使奇数台阶异或为0，于是先手留了奇数台阶异或为0的状态给后手
于是轮到后手：
①当后手移动偶数台阶上的石子时，先手只需将对手移动的石子继续移到下一个台阶，这样奇数台阶的石子相当于没变，于是留给后手的又是奇数台阶异或为0的状态
②当后手移动奇数台阶上的石子时，留给先手的奇数台阶异或非0，根据经典Nim游戏，先手总能找出一种方案使奇数台阶异或为0
因此无论后手如何移动，先手总能通过操作把奇数异或为0的情况留给后手，当奇数台阶全为0时，只留下偶数台阶上有石子。
（核心就是：先手总是把奇数台阶异或为0的状态留给对面，即总是将必败态交给对面）

因为偶数台阶上的石子要想移动到地面，必然需要经过偶数次移动，又因为奇数台阶全0的情况是留给后手的，因此先手总是可以将石子移动到地面，当将最后一个（堆）石子移动到地面时，后手无法操作，即后手失败。

因此如果先手时奇数台阶上的值的异或值为非0，则先手必胜，反之必败！

# 分析2

台阶-Nim游戏
在该 Nim 游戏中，各堆石子对应的有向图游戏不是相互独立的，不能直接使用简单 Nim 游戏的 SG 函数模型，即根据 SG(xi)=xi，判断 x1 ^ x2 ^ ......^ xn

依据分析问题的常规思路，可以尝试将非常规问题化归为已知类型的常规问题，即尝试将有向图游戏相互关联的情况，转化为相互独立的情况，再利用 SG 函数模型加以解决

从该思路出发，尝试分析：

可能存在一些无关的项，使得其变化不影响整体判断，进而将相互关联的有向图游戏分离为若干相互独立的有向图游戏，分离前后不影响整体问题的结果

最原始的情形
n=1，台阶数为 11，显然，和简单Nim 游戏相同，当x0≠0 时，先手必胜

必胜策略：一次性全部拿走

对于更复杂的情形，最底层台阶一定和问题的解直接相关（游戏结束前，必然为2→n 级台阶上的石子全空，仅台阶 11 还剩余石子的情况）

初步扩展
尝试分析n=2 的情形：

x1=0：
先手只能从第二级台阶中拿，不论先手从第二级台阶拿多少，后手均可以将拿到第一级台阶的石子全部放到地上，最终，第二级为空，先手无法继续操作，故先手必败

x1≠0：
先手可以将第一级台阶的石子全部放在地上，此时后手只能从第二级台阶上拿；不论后手从第二级台阶拿多少，先手均可以将拿到第一级台阶的石子全部放到地上，最终，第二级为空，后手无法继续操作，故先手必胜

观察可知，该情形下，相较于n=1 的情形，第二级台阶对先手状态的结果没有产生直接影响

假设
（可以先扩展到 n=3 或n=4 的情形继续观察，更容易得出该假设结论）

偶数级台阶的具体情况可能不影响整个有向图游戏的结果

即：整个有向图游戏的结果，只由奇数级台阶的有向图游戏决定，且这些有向图游戏相互独立（也即：SG(x1) ^ SG(x3) ^ ..... ^ SG(x2k+1) =x=x，k∈N∗k∈N∗，其中 SG(xp)=xp ，若 x≠0x≠0，则先手必胜，否则先手必败）

证明
对于SG(x1) ^ SG(x3) ^ ..... ^ SSG(x2k+1) =x，k∈N∗
显然，终止状态异或和为 0
x≠0，则先手必胜：
与 Nim 游戏类似：

对于先手：

取 x 的最高二进制位 k，则必然存在某一奇数级台阶上的石子数 xt，使得其第k 个二进制位上为 1，在 t 级台阶上取下 xt−(xt−(xt ^ x)x) 个数，使得 xt→xt→ (xt(xt ^ x)x) ，从而使得下一个状态的异或和为 0
对于后手：

若其在某一奇数级台阶上取任意个石子，奇数级台阶对应的异或和必不为 0 （简单 Nim 游戏中得到的结论）
若其在某一偶数级台阶上取任意个石子，则先手只需要在对应的奇数级台阶上取增加的石子数到下一个偶数级台阶，则奇数级台阶对应的异或和不变
由此推知，初始状态下：

各奇数级台阶的石子数异或和为 0，则先手必败
各奇数级台阶的石子数异或和不为0，则先手必胜

 代码

```

#include <iostream>

using namespace std;

int main()
{
int res = 0;
int n;
cin >> n;

for(int i = 1 ; i <= n ; i++)
{
int x;
cin >> x;
if(i % 2) res ^= x;
}

if(res) puts("Yes");
else puts("No");
return 0;
}

```