题目
Alice 和 Bob 正在玩一个异或数列的游戏。
初始时，Alice 和 Bob 分别有一个整数 a 和 b（初始时，a,b 均为 0），有一个给定的长度为 n 的公共数列 $X_1,X_2,⋅⋅⋅,X_n$。
Alice 和 Bob 轮流操作，Alice 先手，每步可以在以下两种选项中选一种：
选项 1：从数列中选一个 $X_i$ 给 Alice 的数异或上，或者说令 a 变为 $a⊕X_i$。（其中 $⊕$ 表示按位异或）
选项 2：从数列中选一个 $X_i$ 给 Bob 的数异或上，或者说令 b 变为 $b⊕X_i$。
每个数 $X_i$ 都只能用一次，当所有 $X_i$ 均被使用后（n 轮后）游戏结束。
游戏结束时，拥有的数比较大的一方获胜，如果双方数值相同，即为平手。
现在双方都足够聪明，都采用最优策略，请问谁能获胜？
输入格式
每个评测用例包含多组询问。询问之间彼此独立。
输入的第一行包含一个整数 $T$，表示询问数。
接下来 T 行每行包含一组询问。其中第 $i$ 行的第一个整数 $ni$ 表示数列长度，随后 $n_i$ 个整数 $X_1,X_2,⋅⋅⋅,X{ni}$ 表示数列中的每个数。
输出格式
输出 T 行，依次对应每组询问的答案。
每行包含一个整数 1、0 或 −1 分别表示 Alice 胜、平局或败。
数据范围
对于所有评测用例，$1≤T≤2×10^5$，$1≤∑X_i≤2×10^5$，$0≤X_i<2^{20}$。
输入样例：
4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580
输出样例：
1
0
1
1
思路
这道题是典型的博弈，如果所有$X_i$的异或和为0，那么他们两者平局
如果异或和不为0，那么可以看作每个二进制位的异或和，那么只需要看哪个位的1的数量为奇数，且该位置靠高位，然后看这个位的1的数量为1，那么先手胜利
如果这个位1的数量大于1，且为奇数，那么可以分为两种情况：
1.总个数为奇数，那么0的个数就为偶数，必然是先手赢，首先取该位为1的数上的，然后变成1的数量偶数，0的数量偶数，看后手取哪部分，先手模仿即可胜利。
2.总个数为偶数的，那么0的个数就为奇数，如果先手取该位为0的数，那么后手模仿，后手胜利，如果先手取该位为1的数，那么就变成第一种情况，后手胜利。
具体看代码。
代码
import java.util.*;
public class Main
{
static int T;
static int[] q = new int[100];
public static void get_bit(int a)
{
int t = 0;
while(a > 0)
{
if(a % 2 == 1)
q[t] ++;
a >>= 1;
t ++;
}
return;
}
public static void main(String[] args) {
Scanner inScanner = new Scanner(System.in);
T = inScanner.nextInt();
while(T --> 0)
{
int n;
int sum = 0;
n = inScanner.nextInt();
Arrays.fill(q, 0);
for(int i = 1; i <= n; i ++)
{
int a = inScanner.nextInt();
get_bit(a);
sum ^= a;
}
if(sum == 0)
System.out.println(0);
else
{
int cnt = -1;
int u = sum;
while(u > 0)
{
cnt ++;
u >>= 1;
}
if(q[cnt] == 1 || (q[cnt] % 2 == 1 && n % 2 == 1))
System.out.println(1);
else
System.out.println(-1);
}
}
inScanner.close();
}
}
/*
3 3
0 3
1 2
0 2
*/
