P13683 【MX-X16-T1】「DLESS-3」XOR and Greater Sum

题目描述

给定长度为 $n$ 的非负整数序列 $a_1, \ldots, a_n$。 小 H 希望选出其中若干个数,使得这些数的按位异或和大于剩下数的按位异或和。小 H 可以选 $0$ 个,此时这些数按位异或和为 $0$;也可以全选,此时剩下的数按位异或和为 $0$。 请你告诉他是否有解。

输入格式

**本题输入包含多组数据。** 第一行,一个整数 $T$,表示数据组数。对于每组数据: - 第一行,一个整数 $n$。 - 第二行,$n$ 个整数 $a_1, \ldots, a_n$。

输出格式

对于每组数据,若有解输出一行一个字符串 `Yes`,否则输出一个字符串 `No`。

说明/提示

**【样例解释】** 对于第一组数据,序列 $a$ 为 $[1, 1, 4, 5, 1, 4]$。我们可以选择子序列 $[5]$,其异或和为 $5$。剩下的数字为 $[1, 1, 4, 1, 4]$,其异或和为 $1\oplus 1\oplus 4\oplus 1\oplus 4=1$。因为 $5>1$,所以有解。 对于第二组数据,序列 $a$ 为 $[1, 1, 4, 5, 1]$。可以证明对于任意一种划分,选出数的异或和总是不大于剩下数的异或和。 对于第三组数据,可以选择子序列 $[9,1]$,其异或和为 $8$。剩下数的异或和为 $1\oplus 9\oplus 8\oplus 1\oplus 0=1$。因为 $8>1$,所以有解。 **【数据范围】** 对于所有数据,保证 $1\le T\le 10^5$,$1\le n,\sum n\le 10^6$,$0\le a_i