← 返回题目列表

Codeforces · 1174/D

D. Ehab 和预期的异或问题

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

给定两个整数 $$$n$$$ 和 $$$x$$$,构造一个满足以下条件的数组:

- 对于数组中的任何元素 $$$a_i$$$,$$$1 \le a_i<2^n$$$;
- 不存在按位异或等于 $$$0$$$ 或 $$$x$$$ 的非空子段,
- 其长度 $$$l$$$ 应该最大化。

序列 $$$b$$$ 是序列 $$$a$$$ 的子段,如果 $$$b$$$ 可以通过从 $$$a$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。

输入

唯一的一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 18$$$, $$$1 \le x<2^{18}$$$)。

输出

第一行应包含数组 $$$l$$$ 的长度。

如果 $$$l$$$ 为正数,则第二行应包含 $$$l$$$ 以空格分隔的整数 $$$a_1$$$、$$$a_2$$$、$$$\dots$$$、$$$a_l$$$ ($$$1 \le a_i < 2^n$$$) — 数组 $$$a$$$ 的元素。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3 5

输出 #1

3
6 1 3

输入 #2

2 4

输出 #2

3
1 3 1

输入 #3

1 1

输出 #3

0

注意

在第一个示例中,子段的按位异或为 $$$\{6,7,4,1,2,3\}$$$。