题目描述

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

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

输入格式
第一行包含整数n。

第二行包含n个数字，其中第 i 个数字表示第 i 堆石子的数量。

输出格式
如果先手方必胜，则输出“Yes”。

否则，输出“No”。

数据范围
1≤n≤105,
1≤每堆石子数≤109

输入样例

2
2 3

输出样例

Yes

其中必败态为每一堆石子的异或和为0
例如： x x+k
第一个人最理想的取法就是第二堆取k个，后手无论取一堆内的多少颗石子，先手都在另一对中取相同数量的石子，最后先手就一定会胜利
一个NIM游戏的变版 http://acm.hdu.edu.cn/showproblem.php?pid=6892

时间复杂度

参考文献

C++ 代码

#pragma GCC optimize(2)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#define lowbit(n) n & (-n)
#define ls x<<1
#define rs x<<1|1
#define clc(a, b) memset(a, b, sizeof(a))
#define Buff ios::sync_with_stdio(false)
#define rush() int Case = 0; int T; scanf("%d", &T);  while(T--)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define per(i, a, b) for(int i = a; i >= b; i --)
#define reps(i, a, b) for(int i = a; b; i ++)
#define read(a) scanf("%d", &a)
#define readd(a) scanf("%lf", &a)
#define readl(a) scanf("%lld", &a)
#define readc(a) scanf("%c", &a)
#define reads(a) scanf("%s", a)
#define sqr(x) x*x
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int>PII;
const int mod = 1e9 + 7;
const double eps = 1e-6;

int main(int argc, char const *argv[])
{
    int n, res = 0;
    read(n);
    rep(i, 0, n-1)
    {
        int x;
        read(x);
        res ^= x;
    }
    puts(res ? "Yes" : "No");
    return 0;
}