seuOJ544 - Xor Division

题目描述

对于一个数组 [a1,a2,...,an](n≥1)[a_1,a_2,...,a_n](\red{n\ge 1}) 来说，定义 f([a1,a2,...,an])=a1⨁a2⨁⋯⨁anf([a_1,a_2,...,a_n])=a_1 \bigoplus a_2 \bigoplus \dots \bigoplus a_n，即数组中所有元素按位异或运算的结果。

给你一个长度为 nn 的数组 aa，请问是否存在一种将数组划分成 k(k>1)k(k>1) 个子数组的方法。假设划分的第 ii 个子数组 bi=[ali,…,ari]b_i=[a_{l_i},\dots,a_{r_i}]，使得所有的划分满足 l1=1,rk=n,li≤ri,li=ri−1+1l_1=1,r_k=n,l_i\le r_i,l_i=r_{i-1}+1 且对于所有划分得到的 kk 个子数组 b1,…,bkb_1,\dots,b_k 来说 f(b1)=⋯=f(bk)f(b_1)=\dots=f(b_k)，即每一个子数组的所有元素的按位异或运算得到的结果相等。

按位异或运算是一种二进制运算方法，用符号 ⊕\oplus 表示。对两个二进制数进行按位异或运算，规则是如果相应位上的两个数字相同则结果为 00 ，如果相应位上的两个数字不同则结果为 11。
例如，假设有两个二进制数 A=1100A = 1100 和 B=1010B = 1010，进行按位异或运算的为 C=0110C = 0110：也就是说，AA 和 BB 的第一位都是 11，所以结果的第一位为 00；AA 的第二位为 11，BB 的第二位为 00，所以结果的第二位为 11；以此类推，可以得到最后的结果 C=0110C = 0110。

Thank you, ChatGPT, for introducing us to bitwise XOR operation.

输入格式

第一行，一个整数 t(1≤t≤104)t(1\le t \le 10^4)，代表数据组数。

对于每组数据：

第一行，一个整数 n(2≤n≤5⋅105)n(\red{2}\le n \le 5\cdot 10^5)，代表数组中数字的数量。

第二行，nn 个整数 a1,a2,…,an(0≤ai≤109)a_1,a_2,\dots,a_n(0\le a_i \le 10^9)，代表数组 aa。

保证同一测试点内 nn 的总和不超过 5⋅1055\cdot 10^5。

输出格式

对于每组数据，假如存在合法的划分方法，输出一行 "YES"，否则输出一行 "NO"。

你可以输出 "YES "和 "NO" 的任何大小写形式（例如，字符串 "yES"、"yes "和 "Yes" 都将被当作肯定的答案）。

样例

输入样例

6
4
1 0 3 2
5
2 1 3 6 5
7
12 8 5 1 4 0 4
2
1 2
6
11 12 12 12 13 2
20
0 5 4 3 4 0 4 6 2 3 1 7 6 6 5 5 3 0 3 7

输出样例

YES
YES
YES
NO
NO
YES

提示
对于样例中第一组数据，可以采取 [[1,0],[2,3]][[1,0],[2,3]] 的划分方式，其中 f(b1)=f(b2)=1⨁0=2⨁3=1f(b_1)=f(b_2)=1\bigoplus 0=2\bigoplus 3=1。

对于样例中第二组数据，可以采取 [[2,1],[3],[6,5]][[2,1],[3],[6,5]] 的划分方式，其中 f(b1)=f(b2)=f(b3)=2⨁1=3=6⨁5=3f(b_1)=f(b_2)=f(b_3)=2\bigoplus 1=3=6\bigoplus 5=3。

对于样例中第三组数据，可以采取 [[12,8],[5,1],[4],[0,4]][[12,8],[5,1],[4],[0,4]] 的划分方式，其中 f(b1)=f(b2)=f(b3)=f(b4)=4f(b_1)=f(b_2)=f(b_3)=f(b_4)=4。