#P17757. XOR Sequence

XOR Sequence

题目描述

小 S 有一个隐藏的整数序列 a0,a1,…,an−1a_0,a_1,\ldots,a_{n-1}。

对于每个 0≤i<n0 \le i < n,都有

0≤ai<230.0 \le a_i < 2^{30}.

对于每个子集 S⊆{0,1,…,n−1}S \subseteq \{0,1,\ldots,n-1\},定义

$$b_S=\mathrm{popcount}\left(\bigoplus_{i\in S} a_i\right),$$

其中 ⊕\oplus 表示按位异或,popcount(x)\mathrm{popcount}(x) 表示 xx 的二进制表示中 11 的个数。

现在给定所有 bSb_S 的值。你需要判断是否存在至少一个满足条件的隐藏序列 aa。

如果不存在,请输出 −1-1。

如果存在,请输出字典序最小的合法序列 aa。

这里字典序按照通常意义定义:若存在一个位置 pp,满足对于所有 0≤i<p0 \le i < p 都有 xi=yix_i=y_i,并且 xp<ypx_p<y_p,则称序列 xx 的字典序小于序列 yy。

输入格式

第一行包含一个整数 TT,表示数据组数。

接下来依次给出 TT 组数据。

每组数据包含两行。

第一行包含一个整数 nn。

第二行包含 2n2^n 个整数:

b0,b1,…,b2n−1.b_0,b_1,\ldots,b_{2^n-1}.

对于一个整数 SS,它的二进制表示描述了对应的子集。若 SS 的第 ii 位为 11,则表示 i∈Si\in S。

输出格式

对于每组数据,输出一行。

若不存在合法序列 aa,输出 −1-1。

否则输出 nn 个整数,表示字典序最小的合法序列

a0,a1,…,an−1.a_0,a_1,\ldots,a_{n-1}.

样例

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

样例解释

第一组数据中,可以取 a=[1,2]a=[1,2]。

四个子集对应的异或值分别为 0,1,2,30,1,2,3,它们的 popcount\mathrm{popcount} 分别为 0,1,1,20,1,1,2。

第二组数据不存在合法序列。

第三组数据中字典序最小的合法序列为 a=[1,3,4]a=[1,3,4]。

第四组数据中,需要满足 popcount(a0)=5\mathrm{popcount}(a_0)=5。满足条件的最小非负整数为 3131。

数据范围

对于所有测试数据,满足:

1≤T≤5,1 \le T \le 5, 1≤n≤20,1 \le n \le 20, 0≤bS≤30.0 \le b_S \le 30.

本题共有 2020 个测试点,每个测试点 55 分。各测试点不捆绑计分。

测试点编号 分值 n≤n\leq 特殊性质
1 5 11 A
2 无
3 22 A
4 无
5 33 A
6 无
7 44 A
8 无
9 66 A
10 无
11 88 A
12 无
13 1010 A
14 无
15 1212 A
16 无
17 1515 A
18 无
19 2020 A
20 无

特殊性质 A:保证存在至少一个合法序列 aa。