很好的构造题。
题意
请构造一个长度为 $2^{m+1}$ 的序列 $a$，该序列满足：
- $\forall i \in[1, 2^{m+1}], a_i \in [0, 2^m-1]$ 且每个数都恰好出现两次。
- 对于任意一对 $(i, j)$ 满足 $a_i = a_j$，$a_i\oplus a_{i+1} \oplus \cdots \oplus a_{j-1} \oplus a_j = k$。
$\oplus$ 表示按位异或。
思路
很显然，当 $k>2^m-1$ 时无解。
再考虑平凡的的情况：
- 当 $m$ 为 $0$，$k$ 为 $0$ 时，只有
0 0一组解。 - 当 $m$ 为 $1$，$k$ 为 $0$ 时，样例告诉我们只有
0 0 1 1一组解。 - 当 $m$ 为 $1$，$k$ 为 $1$ 时，样例告诉我们无解。
接下来考虑一般情况：
我们知道，$a \oplus a$ 为零，所以只需构造一个序列形如：
$$ 0,1 \dots 2m-1,k,2m-1 \dots 1,0,k $$
该式满足：对于任意一对 $(i, j)$，$a_i = a_j$，$a_i\oplus a_{i+1} \oplus \cdots \oplus a_{j-1} \oplus a_j = k$。
显然，这个序列除最后一个元素外是回文的，并且所有数字都出现了 $2$ 次，正好可以相互抵消。
对于 $k$ 形成的子序列，有一个公式：$0\oplus 1 \oplus 2 \oplus \dots \oplus k=0$，因为在 $0$ 至 $k$ 的序列中，每一位上都出现了偶数个 $1$，全部抵消后便为 $k \oplus 0=k$。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,s,d[100005],f;
ll ans;
int main(){
scanf("%lld%lld",&a,&s);
if(a==1&&s==0){
printf("0 0 1 1");
return 0;
}
if(s>=pow(2,a)){
printf("-1");
return 0;
}
for(int i=0;i<pow(2,a);i++){
if(i==s) continue;
printf("%lld ",i);
}
printf("%lld ",s);
for(int i=pow(2,a)-1;i>=0;i--){
if(i==s) continue;
printf("%lld ",i);
}
printf("%lld",s);
return 0;
}