AT_abc126_f [ABC126F] XOR Matching

题目描述

请构造一个长度为 $2^{M+1}$ 的数列 $a = \{a_1, a_2, \ldots, a_{2^{M+1}}\}$，使其满足以下条件（如果存在的话，请构造出其中一种）：

• $a$ 包含 $0$ 以上小于 $2^M$ 的每个整数各恰好 $2$ 次。
• 对于任意满足 $a_i = a_j$ 的 $i, j\ (i < j)$，都有 $a_i\ xor\ a_{i+1}\ xor\ \cdots\ xor\ a_j = K$。

其中，$xor$ 表示异或运算。

异或（$xor$）的定义如下：

对于整数 $c_1, c_2, \ldots, c_n$，$c_1\ xor\ c_2\ xor\ \cdots\ xor\ c_n$ 的二进制表示中，第 $2^k$ 位（$k \geq 0$）的数是：如果 $c_1, c_2, \ldots, c_n$ 中二进制表示的第 $2^k$ 位为 $1$ 的数的个数为奇数，则该位为 $1$，否则为 $0$。

例如，$3\ xor\ 5 = 6$（二进制表示为：011 $xor$ 101 $=$ 110）。

输入格式

输入为一行，包含两个整数 $M$ 和 $K$。

输出格式

如果不存在满足条件的数列 $a$，输出 -1。

如果存在，输出 $a$ 的元素，空格分隔。

如果有多个满足条件的数列，输出任意一个均可。

样例 1

输入

1 0

输出

0 0 1 1

样例 2

输入

1 1

输出

-1

样例 3

输入

5 58

输出

-1

说明/提示

限制

• 输入均为整数。
• $0 \leq M \leq 17$
• $0 \leq K \leq 10^9$

样例解释 1

在本例中，存在多个满足条件的数列。例如 $a = \{0, 0, 1, 1\}$，对于 $a_i = a_j$ 的 $(i, j)\ (i < j)$，有 $(1, 2)$ 和 $(3, 4)$。$a_1\ xor\ a_2 = 0, a_3\ xor\ a_4 = 0$，因此该 $a$ 满足条件。

样例解释 2

不存在满足条件的数列。

样例解释 3

不存在满足条件的数列。

由 ChatGPT 4.1 翻译