← 返回题目列表

AtCoder · abc126_f

F. 异或匹配

中文机器翻译题面 查看原题

分数: 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

没有序列满足条件。