XOR Matching

题目描述

构造一个长度为 $2^{M + 1}$ 的序列 $a$ = {$a_1,\ a_2,\ ...,\ a_{2^{M + 1}}$}，使其满足以下条件（如果存在这样的序列）。

每个在 $0$ 到 $2^M - 1$（含）之间的整数在 $a$ 中恰好出现两次。 对于任意满足 i < j 且 $a_i = a_j$ 的 $i,j$，有公式 $a_i \ xor \ a_{i + 1} \ xor \ ... \ xor \ a_j = K$ 成立。

什么是 xor（按位异或）？

整数 $c_1, c_2, ..., c_n$ 的 xor 定义如下：

当 $c_1 \ xor \ c_2 \ xor \ ... \ xor \ c_n$ 用二进制表示时，$2^k$ 位上的数字（$k \geq 0$）是 $1$ 当且仅当在 $c_1, c_2, ...c_m$ 中其二进制表示在 $2^k$ 位上为 $1$ 的整数个数为奇数，否则为 $0$。

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

输入格式

从标准输入读入，格式如下： $M$ $K$

输出格式

如果不存在满足条件的序列 $a$，输出 $-1$。 如果存在这样的序列 $a$，输出任意满足条件的序列 $a$ 的元素，元素间用空格分隔。 如果存在多个满足条件的序列，输出其中任意一个即可。

1 0

0 0 1 1

1 1

-1

5 58

-1

提示

输入中的所有数值均为整数。 $0 \leq M \leq 17$ $0 \leq K \leq 10^9$对于这一用例，存在多个满足条件的序列。 例如，当 $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$ 满足条件。
不存在满足条件的序列。
不存在满足条件的序列。

标签: AtCoder|abc126F

来源

AtCoder|abc126F