题目：https://codeforces.com/contest/1174/problem/D

D. Ehab and the Expected XOR Problem

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Given two integers n and x, construct an array that satisfies the following conditions:

  • for any element ai in the array, 1≤ai<2n;
  • there is no non-empty subsegment with bitwise XOR equal to 0 or x,
  • its length l should be maximized.

A sequence b is a subsegment of a sequence a if b can be obtained from a by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

The only line contains two integers n and x (1≤n≤18, 1≤x<218).

Output

The first line should contain the length of the array l.

If l is positive, the second line should contain l space-separated integers a1, a2, …, al (1≤ai<2n) — the elements of the array a.

If there are multiple solutions, print any of them.

Examples

input

Copy

3 5

output

Copy

3
6 1 3

input

Copy

2 4

output

Copy

3
1 3 1

input

Copy

1 1

output

Copy

0

Note

In the first example, the bitwise XOR of the subsegments are {6,7,4,1,2,3}.

 

题意：给你两个数字n和x，构造一个数组使得他们的任意子段异或和不等于0和x，对于每个数a[i],有1<=a[i]<2^n，要求构造的这              个数组尽可能的长。

当时比赛的时候看到这个题目完全就找不到方向，不知道该往哪一个方向去思考。后来看了题解，觉得这个解题思路很有趣，于是打算写一篇博客留着以后看看。

 

思路：考虑构造这个数组本身的话，感觉是力不从心，不知如何下手。换个想法，1---2^n之间的数异或和肯定也是在这个范围之            内，那我们就构造这个数组的异或前缀和，因为任意子段异或和不能等于0，所以我们构造的这个异或前缀数组里面就不能有两个相同的数，如果x>=2^n，显然我们可以取1--2^n之间的所有数，也就是2^n-1个；如果x是在1--2^n这个范围内的话，假如我们选取一个数k的话，那么k^x肯定就不能选了，因为如果选了的话就会导致异或和会出现x，不合法。 于是我们从1--n依次选一个数作为前缀和，同时标记一下k^x，下次再遇上的话就不再选。把前缀异或和数组构造出来之后，相邻两个数再异或一下即可构造出符合要求的答案。具体参看代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1000 * 1000 + 10;
int a[maxn], b[maxn];
int n, x;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	memset(b,0,sizeof(b));
	cin >> n >> x;

	b[x] = 1;               //构造的数组肯定不能有x，很显然的
	int cnt = 1;
	for (int i = 1; i < (1 << n); i++) {
		if (b[i])continue;				//如果这个数已经被标记过了，就不选
		b[i] = 1; b[i^x] = 1;   //选择i之后，那么i^x啃的就不能选了，标记一下，下次就可以不用选了
		a[cnt++] = i;    //记录选的这个数
	}

	cout << cnt - 1 << endl;
	for (int i = 1; i < cnt; i++)cout << (a[i] ^ a[i - 1]) << ' ';   //根据前缀和的构造，a[i]^a[i-1]就是第i个数

	cout << endl;

	return 0;
}