CF1174D Ehab and the Expected XOR Problem

Description

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
3 5
output
3
6 1 3
input
2 4
output
3
1 3 1
input
1 1
output
0

Note

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

题意：
  构造一个数列，元素为1~2^n的数，使得数列的任意子段的XOR和均不等于0与X。求数列的长度和任意一个解。

思路：
  最重要的：想到取构造前缀XOR和数组，而非直接去构造数组ai。
  具体的：构造前缀XOR和数组bi，则al^al+1···^ar=bl-1br.则不等于0->任意的bi与bj不相等。不等于X->若bi^bj=X，则只能取其一（代码中取了更小的）。遍历一遍所有数即可。然后用前缀数组算出原数组。
  时间复杂度O（2^n）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e6+10;
int n,x,t[maxn],num,f[20],cou[maxn];//cou为输出，t[i]=1表示数组b不能选i，实际上用一个即可

int main()
{
    cin>>n>>x;
    t[0]=t[x]=1;
    for(int i=1;i<(ll)(pow(2,n));i++)
        if(t[i]==0)
            cou[++num]=i,t[x^i]=1;//i^j=x <==> i^x=j ,让之后选的数不为i^x或x就行
    cout<<num<<endl;
    if(num!=0)
        cout<<cou[1]<<' ';
    for(int i=1;i<num;i++)
        cout<<(cou[i]^cou[i+1])<<' ';
    return 0;
}