简单题*10000

Description

 已知一排硬币中有n个硬币正面朝上，输入正面朝上的硬币的位置ai（可能重复）。两人轮流操作，每次操作可以翻转1,2,或则3枚硬币（不一定连续），其中翻转的最右的硬币必须是正面朝上的，最后不能翻转的为负

Input

 第一行输入一个组数t（t ≤ 100）。

对于每组数据第一行有一个正整数N(0 ≤ N ≤ 5000)。

第二行N个非负整数c1,c2,...,cN(0 ≤ ai ≤ 1e9)。

Output

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

Sample Input

2 1 0 4 0 1 2 3

Sample Output

Yes No

HINT

题解

定义硬币全反时的sg为0，现在单个游戏就是只有一枚硬币朝上，其余都是反，其他情况都可以由单一游戏组合而成。如果位置i有一个正面朝上的硬币，其余都是反，那么这枚硬币翻过来的时候，它可以到达的局面是1、sg = 0   2、sg(j)j位置的硬币朝上，其余都是反（j<i） 3、出现两个正面朝上的硬币，变成组合游戏sg(j)和sg(k)。我们把sg函数打表出来就可以找到规律。（hdu3537）

初始编号从0开始。

当N==1时，硬币为：正，先手必胜，所以sg[0]=1.

当N==2时，硬币为：反正，先手必赢，先手操作后可能为：反反或正反，方案数为2，所以sg[1]=2。

当N==3时，硬币为：反反正，先手必赢，先手操作后可能为：反反反、反正反、正反正、正正反，方案数为4，所以sg[2]=4。

位置x：0  1  2  3  4   5    6   7    8     9  10  11  12  13  14...

sg[x]：  1  2  4  7  8  11 13 14  16  19  21  22  25  26  28…

看上去sg值为2x或者2x+1。我们称一个非负整数为odious，当且仅当该数的二进制形式的1出现的次数是奇数，否则称作evil。所以1，2，4，7是odious因为它们的二进制形式是1,10,100,111.而0,3,5,6是evil，因为它们的二进制形式是0,11,101,110。而上面那个表中，貌似sg值都是odious数。所以当2x为odious时，sg值是2x，当2x是evil时，sg值是2x+1.

这样怎么证明呢？我们会发现发现，

                                                     evil^evil=odious^odious=evil

                                                     evil^odious=odious^evil=odious

假设刚才的假说是成立的，我们想证明下一个sg值为下一个odious数。注意到我们总能够在第x位置翻转硬币到达sg为0的情况；通过翻转第x位置的硬币和两个其它硬币，我们可以移动到所有较小的evil数，因为每个非零的evil数都可以由两个odious数异或得到；但是我们不能移动到下一个odious数，因为任何两个odious数的异或都是evil数。

假设在一个Mock Turtles游戏中的首正硬币位置x1,x2,…,xn是个P局面，即sg[x1]^…^sg[xn]=0.那么无可置疑的是n必定是偶数，因为奇数个odious数的异或是odious数，不可能等于0。而由上面可知sg[x]是2x或者2x+1，sg[x]又是偶数个，那么x1^x2^…^xn=0。相反，如果x1^x2^…^xn=0且n是偶数，那么sg[x1]^…^sg[xn]=0。这个如果不太理解的话，我们可以先这么看下。2x在二进制当中相当于把x全部左移一位，然后补零，比如说2的二进制是10，那么4的二进制就是100。而2x+1在二进制当中相当于把x全部左移一位，然后补1，比如说2的二进制是10，5的二进制是101。现在看下sg[x1]^…^sg[xn]=0，因为sg[x]是2x或者2x+1，所以式子中的2x+1必须是偶数个（因为2x的最后一位都是0,2x+1的最后一位都是1，要最后异或为0,2x+1必须出现偶数次）

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll inff = 0x3f3f3f3f3f3f3f3f;
#define FOR(i,a,b) for(int i(a);i<=(b);++i)
#define FOL(i,a,b) for(int i(a);i>=(b);--i)
#define REW(a,b) memset(a,b,sizeof(a))
#define inf int(0x3f3f3f3f)
#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define ss(a) scanf("%s",a)
#define mod ll(6666666)
#define pb push_back
#define eps 1e-6
#define lc d<<1
#define rc d<<1|1
#define Pll pair<ll,ll>
#define P pair<int,int>
#define pi acos(-1)
int n,a[100008];
int as(int x)
{
    int k=0;
    while (x)
    {
        if (x&1) k++;
        x>>=1;
    }
    return !(k&1);
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    //freopen("game001.in","r",stdin);
    //freopen("game001.out","w",stdout);
    int tt;
    cin>>tt;
    while(tt--)
    {
        si(n);
        FOR(i,1,n) si(a[i]);
        sort(a+1,a+n+1);
        int k=unique(a+1,a+n+1)-a-1,s=0;
        FOR(i,1,k)
        {
            a[i]*=2ll;
            if(as(a[i])) a[i]++;
            s^=a[i];
        }
        if(s) puts("Yes");
        else puts("No");
    }
    return 0;
}