[ABC126F] XOR Matching

请构造一个长度为 2^m+1 的序列 a 满足

• ∀i∈[1,2m+1],ai​∈[0,2m−1] 且每个数都恰好出现两次。
• 对于任意一对 (i,j) 满足 ai​=aj​，ai​⊕ai+1​⊕⋯⊕aj−1​⊕aj​=k

⊕⊕ 表示按位异或。

输入输出样例

输入 #1复制

1 0

输出 #1复制

0 0 1 1

输入 #2复制

1 1

输出 #2复制

-1

输入 #3复制

5 58

输出 #3复制

-1

 

容易发现 k≥2m 时显然无解。

接下来先处理些平凡的情况。

• m=0，k=0：显然只有 0 0 这一组解；
• m=1，k=0：样例给了 0 0 1 1 这一组解；
• m=1，k=1：样例告诉我们无解。

现在开始考虑 m≥2 的情况，考虑构造一个 k⊕0=k 的形式。

注意到 x⊕x=0，于是考虑按如下对称形式构造：

0,1,…,k−1,k+1,…,2m−1,k,2m−1,…,k+1,k−1,…,1,0,k

对于除了 �k 以外的数字，它们形成的子序列是完全对称的，除了 k 之外的数字每个数字均出现恰好两次，于是全部抵消，形成了 k⊕0=k 的形式。

对于 k 来说，它形成的子序列中，0∼2m−1 中除了 k 之外每个数字只出现一次，k 出现两次。注意到 0∼2m−1 的异或和总为零（对于每一个二进制位，满足该位上值为 1 的数恰好有 2m−1 个，总是偶数），于是最后还是 k⊕0=k 的形式。

 

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
int main(){int m,k;scanf("%d %d",&m,&k);if(m==1){ //特判 if(k==0) printf("0 0 1 1");else printf("-1");return 0;}if(k>=pow(2,m)){printf("-1");return 0;}for(int i=0;i<pow(2,m);i++){ //正序 if(i==k) continue; //不输出k printf("%d ",i);}printf("%d ",k);for(int i=pow(2,m)-1;i>=0;i--){ //倒序 if(i==k) continue; //不输出k printf("%d ",i);}printf("%d ",k);return 0;
}