分数: 600 点
问题陈述
构造一个序列 a = {a_1,\ a_2,\ ...,\ a_{2^{M + 1}}} 长度 2^{M + 1} 满足以下条件(如果存在这样的序列)。
- 之间的每个整数 0 和 2^M - 1 (含)出现两次 a.
- 对于任何 i 和 j (i < j) 这样 a_i = a_j,公式 a_i \ xor \ a_{i + 1} \ xor \ ... \ xor \ a_j = K 成立。
什么是异或(按位异或)?
整数的异或 c_1, c_2, ..., c_n 定义如下:
- 当 c_1 \ xor \ c_2 \ xor \ ... \ xor \ c_n 以基数 2 书写,即 2^k的地点 (k \geq 0)是 1 如果其中的整数个数 c_1, c_2, ...c_m 其二进制表示有 1 在 2^k的位置是奇数,并且 0 如果该计数是偶数。
例如, 3 \ xor \ 5 = 6。 (如果我们用二进制写: 011 xor 101 = 110.)
约束
- 输入中的所有值都是整数。
- 0 \leq M \leq 17
- 0 \leq K \leq 10^9
输入
输入由标准输入按以下格式给出:
M K
输出
如果没有序列 a 满足条件,打印 -1.
如果存在这样的序列 a,打印一个这样的序列的元素 a 之间有空格。
如果有多个序列满足条件,则其中任何一个都将被接受。
示例输入 1
1 0
示例输出 1
0 0 1 1
对于这种情况,有多个序列满足条件。
例如,当 a = {0, 0, 1, 1},有两对 (i,\ j)\ (i < j) 这样 a_i = a_j: (1, 2) 和 (3, 4)。自从 a_1 \ xor \ a_2 = 0 和 a_3 \ xor \ a_4 = 0,这个序列 a 满足条件。
示例输入 2
1 1
示例输出 2
-1
没有序列满足条件。
示例输入 3
5 58
示例输出 3
-1
没有序列满足条件。