#P17757. XOR Sequence
XOR Sequence
题目描述
小 S 有一个隐藏的整数序列 。
对于每个 ,都有
对于每个子集 ,定义
$$b_S=\mathrm{popcount}\left(\bigoplus_{i\in S} a_i\right),$$其中 表示按位异或, 表示 的二进制表示中 的个数。
现在给定所有 的值。你需要判断是否存在至少一个满足条件的隐藏序列 。
如果不存在,请输出 。
如果存在,请输出字典序最小的合法序列 。
这里字典序按照通常意义定义:若存在一个位置 ,满足对于所有 都有 ,并且 ,则称序列 的字典序小于序列 。
输入格式
第一行包含一个整数 ,表示数据组数。
接下来依次给出 组数据。
每组数据包含两行。
第一行包含一个整数 。
第二行包含 个整数:
对于一个整数 ,它的二进制表示描述了对应的子集。若 的第 位为 ,则表示 。
输出格式
对于每组数据,输出一行。
若不存在合法序列 ,输出 。
否则输出 个整数,表示字典序最小的合法序列
样例
4
2
0 1 1 2
2
0 1 0 0
3
0 1 2 1 1 2 3 2
1
0 5
1 2
-1
1 3 4
31
样例解释
第一组数据中,可以取 。
四个子集对应的异或值分别为 ,它们的 分别为 。
第二组数据不存在合法序列。
第三组数据中字典序最小的合法序列为 。
第四组数据中,需要满足 。满足条件的最小非负整数为 。
数据范围
对于所有测试数据,满足:
本题共有 个测试点,每个测试点 分。各测试点不捆绑计分。
| 测试点编号 | 分值 | 特殊性质 | |
|---|---|---|---|
| 1 | 5 | A | |
| 2 | 无 | ||
| 3 | A | ||
| 4 | 无 | ||
| 5 | A | ||
| 6 | 无 | ||
| 7 | A | ||
| 8 | 无 | ||
| 9 | A | ||
| 10 | 无 | ||
| 11 | A | ||
| 12 | 无 | ||
| 13 | A | ||
| 14 | 无 | ||
| 15 | A | ||
| 16 | 无 | ||
| 17 | A | ||
| 18 | 无 | ||
| 19 | A | ||
| 20 | 无 |
特殊性质 A:保证存在至少一个合法序列 。