题目附件

附件与本题使用相同的访问权限。

暂无附件。

#3. 异或合并

异或合并

异或合并

英文名:AGAGA XOOORRR

题目描述

小 A 非常喜欢一种“异或合并”操作。给定一个长度为 nn 的非负整数数组 aa。

每次操作,他可以选取相邻的两个元素,将它们删除,并在原来的位置放入这两个数的按位异或(bitwise XOR)结果。数组的长度因此减少 11。

小 A 想知道:能否通过若干次(可以为零次)这样的操作,使得数组中剩余的所有元素都相等?由于他要求“至少剩下两个元素”,所以最终数组的长度必须 不小于 22。

若可以做到,输出 YES;否则输出 NO。

输入格式

第一行一个整数 tt,表示测试组数。

对于每组测试数据:

  • 第一行一个整数 nn,表示数组长度;
  • 第二行 nn 个用空格分隔的整数 a1,a2,…,ana_1, a_2, \ldots, a_n。

输出格式

对每组测试数据,输出一行 YES 或 NO。

样例

样例 1

输入:

2
3
0 2 2
4
2 3 1 10

输出:

YES
NO

说明:

  • 第一组:先合并前两个元素,0⊕2=20 \oplus 2 = 2,数组变为 [2,2][2, 2],两个元素相等,剩余 22 个元素,满足要求。
  • 第二组:无论如何操作,都无法使剩余元素全部相等。

样例 2

输入:

3
2
5 5
3
1 2 4
5
4 1 5 6 2

输出:

YES
NO
YES

说明:

  • 第一组:[5,5][5,5] 已经全部相等且剩余 22 个元素,输出 YES。
  • 第二组:[1,2,4][1,2,4] 的总异或为 1⊕2⊕4=71 \oplus 2 \oplus 4 = 7。无论怎么合并,都无法留下至少两个相等的元素,输出 NO。
  • 第三组:可以分成三段 [4][4]、[1,5][1,5]、[6,2][6,2],它们的异或和都为 44,最终可得到 3 个相等的元素,输出 YES。

数据范围与约定

全局约束:

  • 1≤t≤151 \le t \le 15;
  • 2≤n≤20002 \le n \le 2000;
  • 0≤ai<2300 \le a_i < 2^{30}。

子任务:

子任务 分值 约定
1 30 n≤12n \le 12
2 70 无额外限制