台阶NIM游戏

台阶NIM游戏是NIM游戏的变种，如果不清楚NIM游戏是什么请看上篇文章

确保理解经典NIM游戏之后来分析本例

对于台阶NIM游戏有如下结论

台阶NIM游戏可以看做是对所有奇数级台阶做经典NIM游戏

结论可以证明，如下：

证法一

要证明上述结论只需证明

1. 对偶数级台阶的操作和游戏结果没有关系
2. 奇数级台阶的博弈问题等价于经典NIM游戏

先证明第一条：

对于对手对偶数级台阶的某次操作（将2n号台阶上的石子拿下x个到2n-1号上），我们都可以对下一级台阶采取同样操作使其无效（将2n-1号的x个石子拿到2n-2上）

这样便可令偶数级台阶的操作不会影响到奇数级台阶

而根据题意，地面上（0级）台阶是不可操作的，所以对手只能操作2,4,6，···等台阶，而操作这些台阶的结果最终都会收敛到操作第二级台阶，即：对手将第二级台阶的若干石子移至第一级，我们这时将同样数量的石子移至地面，无效化他的操作

这样的情况会收敛于偶数台阶均为0（不可操作）的状态，所以偶数级台阶的状态对游戏结果没有关系

再证明第二条： 对于对手对奇数级台阶的某次操作（将2n+1号台阶上的石子拿下x个到2n号上），可以看做是在经典NIM游戏中将这堆石子取走——因为偶数级台阶相当于“垃圾桶”，进来的石子都对胜负结果没有影响

所以我们可以直接套用经典NIM游戏的结论：

台阶NIM游戏先手必胜，当且仅当所有奇数级台阶石子数异或和不等于0

证法二

因为第k级台阶上的石子需要k次移动才可以到地面（退出游戏），所以第k级台阶上的n个石子可以看做经典NIM游戏中的k个石子堆，每堆石子有n个

当k是偶数时，k个相同的石子堆之间异或和为0 当k是奇数时，k个相同的石子堆之间异或和为n

所以命题得证，即——台阶NIM游戏可以看做是对所有奇数级台阶做经典NIM游戏

上原题代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int res = 0;
    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;
}