异或数列

题目描述：

给定一个数组ar[i]，Alice和Bob轮流操作，Alice先操作，每次操作，都会选择一个数异或当前这个人有的数，二者的值初始化都是0，每个数只能用一次，问最后谁的数大

思路：

不难发现，转换成二进制后，如果有谁最后能获得最高位的1，那不管剩下的位置的数字如何，它一定可以获胜，例如：Alice能抢到最高位的数字：8,Bob抢不到，但是Bob有1，2，4，这加起来也才是7，所以高位即王道。

那怎么判断高位能不能抢到呢？

我们统计出来n个数字中每一位是的1的数量和，如果当前这位的数量num是奇数，那有两种情况先手必赢：

• 数量是1，此时Alice先手，可以直接选这个高位，然后直赢

• 看n的奇偶性，奇数先手直赢，偶数先手必输

  • n是奇数，此时Alice可以直接选一个最大的值，此时Bob有两种情况可以选择

    • Bob也选最大的那个，那这样的操作就相当于num -= 2
    • Bob不选最大的那个，因为n奇数,num奇数，所以n - num是偶数，下一次的Alice可以通过镜像操作，也不选最大值，相当于num -= 0，也就是不变

    不难发现，num一定是以减去2的形式直到剩下1个最大值，此时因为Alice先手，那就是Alice直赢

  • n是偶数，情况和上次类似，Alice不论选最大值还是不是最大值的数，Bob都可以通过镜像操作，使的变成Bob先手，n是奇数，num也是奇数的必胜局面，此时就是Bob直赢

如果当前的最大值的数量num是偶数，那二者可以通过镜像操作，使的这个最大值无法被对方抢到，相当于这个值不存在，那我们只需要看下一个最大值即可，依次类推

什么时候是平局？

只有当所有数字的异或和是0时，才会是平

//Work by: Chelsea
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
ll a, b, c;
string s, t;
int tr[30];

void work(){
    cin >> n;
    int sum = 0;
    mem(tr, 0);
    for(int i = 1; i <= n; ++i){
        cin >> x;
        sum ^= x;
        for(int j = 0; j <= 20; ++j){
            int p = (x & (1<<j));
            if(p)++tr[j];
        }
    }
    if(sum == 0){
        cout << 0 << endl;
        return;
    }
    for(int j = 20; j >= 0; --j){
        if(tr[j] % 2 == 1){
            if(n % 2 == 1 || tr[j] == 1){
                cout << 1 << endl;
            }
            else cout << -1 << endl;
            return;
        }
    }
    cout << -1 << endl;
}


int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}