台阶-Nim游戏

在该 $Nim$ 游戏中，各堆石子对应的有向图游戏不是相互独立的，不能直接使用简单 $Nim$ 游戏的 $SG$ 函数模型，即根据 $SG(x_i)=x_i$，判断 $x_1$ ^ $x_2$ ^ ......^ $x_n$

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

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

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

最原始的情形

$n=1$，台阶数为 $1$，显然，和简单 $Nim$ 游戏相同，当 $x_0\ne0$ 时，先手必胜

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

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

初步扩展

尝试分析 $n=2$ 的情形：

• $x_1=0$：

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

• $x_1\ne 0$：

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

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

假设

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

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

即：整个有向图游戏的结果，只由奇数级台阶的有向图游戏决定，且这些有向图游戏相互独立（也即：$SG(x_1)$ ^ $SG(x_3)$ ^ ..... ^ $SG(x_{2k+1})$ $=x$，$k\in N^*$，其中 $SG(x_p)=x_p$ ，若 $x\ne 0$，则先手必胜，否则先手必败）

证明

对于 $SG(x_1)$ ^ $SG(x_3)$ ^ ..... ^ $SG(x_{2k+1})$ $=x$，$k\in N^*$

显然，终止状态异或和为 $0$

$x\ne 0$，则先手必胜：

与 $Nim$ 游戏类似：

对于先手：

取 $x$ 的最高二进制位 $k$，则必然存在某一奇数级台阶上的石子数 $x_t$，使得其第 $k$ 个二进制位上为 $1$，在 $t$ 级台阶上取下 $x_t-(x_t$ ^ $x)$ 个数，使得 $x_t\to$ $(x_t$ ^ $x)$ ，从而使得下一个状态的异或和为 $0$

对于后手：

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

由此推知，初始状态下：

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

示例代码

数据加强后检测到原代码while循环存在错误，已修改，感谢评论提醒

#include <iostream>
#include <algorithm>
using namespace std;
int n, x, ans;

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    cin >> n;

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

    if(ans) cout << "Yes";
    else cout << "No";

    return 0;
}