CF-1075-C2. XOR-convenience (Hard Version)（打表，错误的时候可以输出错误的地方）（如果说已经构造出来了简单版，复杂版可能也只需要微调） · znzryb
## 题目大意
### 题目总结
**问题描述**
给定一个正整数 $n$（$3 \le n \le 2 \cdot 10^5$）。你需要构造一个长度为 $n$ 的**排列** $p$（包含 $1$ 到 $n$ 的所有整数各一次），使得对于每一个 $i$（$1 \le i \le n-1$），都能在索引范围 $[i, n]$ 中找到一个下标 $j$（即 $i \le j \le n$），满足以下异或条件：
$$
p_i = p_j \oplus i
$$
如果不存在满足条件的排列，则输出 $-1$。
**输入输出**
- **输入**：测试用例数量 $t$，每个案例包含一个整数 $n$。
- **输出**：若存在，输出 $n$ 个整数表示排列 $p$；否则输出 $-1$。
---
**样例解释**
以 $n=3$ 为例，输出为 `2 1 3`：
- 当 $i=1$ 时：需要存在 $j \in \{1, 2, 3\}$ 使得 $p_1 = p_j \oplus 1$。
已知 $p_1=2$，若取 $j=3$，则 $p_3 \oplus 1 = 3 \oplus 1 = 2$。满足条件。
- 当 $i=2$ 时：需要存在 $j \in \{2, 3\}$ 使得 $p_2 = p_j \oplus 2$。
已知 $p_2=1$，若取 $j=3$，则 $p_3 \oplus 2 = 3 \oplus 2 = 1$。满足条件。
- 所有 $i \in [1, 2]$ 均满足条件，故 `2 1 3` 是合法解。
以 $n=4$ 为例：
- 不存在任何长度为 $4$ 的排列能满足上述所有约束，故输出 $-1$。
## 思路讲解
这道题目，一种方法是打表找规律，比较神秘，呃，也比较费时间，只不过由于我 C1 是打表打出来的，C2 也这样子尝试了，由于选取的规律比较奇怪，在某些情况下会出现问题，后需要与下标 $\text{lowbit}(n)$ 交换啊什么的，在这里就不介绍了。
不过可以总结一下，就是这种打表找规律的话，首先要确定没有答案的条件，其次就是**写的检查器尽量报出更多的信息**（在错误时），比如说这道题目，如果你构造出来的序列是错的，你写的检查器最好要报出来哪一位错了，有哪些位构造错误？这一位你填了什么值？反正信息越多越好。
那么构造方法如何解决 C1 呢？那么由于是要求 $p_i = p_j \oplus i$，不妨就令 $p_i=i\oplus 1$，把 1 放在最后就可以了，最后这样子生成的序列第一位可能有点问题，这个特判一下就行。
那么如果你会解决 C1 的话，其实只需要增加一行代码：
```cpp
if (N%2==0) {
ans_ls[1]=N;
swap(ans_ls[1],ans_ls[lowbit(N)]);
}else {
ans_ls[1]=N-1;
}
```
即 `swap(ans_ls[1],ans_ls[lowbit(N)]);` 这一行代码。首先 $\text{lowbit}(n)\oplus 1$ 肯定不愁找不到满足的 $j$，因为他都处于第一个位置了。那么对于 $n$ 呢？那么由于 $n≥n\oplus \text{lowbit}(n)≥\text{lowbit}(n)+2$（$n$ 是偶数），所以说也不用愁找不到 $j$。
当然，注意，$n$ 是 2 的幂次的时候是没有答案的，这也很容易理解，因为这个时候 $n$ 无论异或上 $[1,n]$ 中的任何一个数字，其结果都超过了 $[1,n]$ 的范围。
## AC代码
AC
[https://codeforces.com/contest/2189/submission/359568527](https://codeforces.com/contest/2189/submission/359568527)
::: 源代码（构造）
```cpp
/**
* Problem: C2. XOR-convenience (Hard Version)
* Contest: Codeforces Round 1075 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2189/problem/C2
* Created: 2026-01-24 14:18:16
* Author: Gospel_rock
*/
#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
ll lowbit(ll x) {
return x&-x;
}
void Solve() {
ll N;
cin >> N;
if (has_single_bit((unsigned)N)) {
cout<<-1<<"\n";
return;
}
vector<ll> ans_ls(N+2);
for (int i=2;i<=N-1;++i) {
ans_ls[i]=i^1;
}
ans_ls[N]=1;
if (N%2==0) {
ans_ls[1]=N;
swap(ans_ls[1],ans_ls[lowbit(N)]);
}else {
ans_ls[1]=N-1;
}
for (int i=1;i<=N;++i) {
cout<<ans_ls[i]<<" ";
}
cout<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2189/submission/359568527
*/
```
:::
AC
[https://codeforces.com/contest/2189/submission/359512601](https://codeforces.com/contest/2189/submission/359512601)
::: 源代码（打表找规律）
```cpp
/**
* Problem: C2. XOR-convenience (Hard Version)
* Contest: Codeforces Round 1075 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2189/problem/C2
* Created: 2026-01-24 14:37:06
* Author: Gospel_rock
*/
#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
ll lowbit(ll x) {
return x&-x;
}
void Solve() {
ll N;
cin >> N;
if (has_single_bit((unsigned)N)) {
cout<<-1<<"\n";
return;
}
vector<ll> ans_ls(N+2);
if (N&1) {
ans_ls[1]=N-1;
ans_ls[N]=1;
queue<ll> q_ji,q_ou;
for (int i=2;i<=N-2;++i) {
if (i&1) {
q_ji.push(i);
}else {
q_ou.push(i);
}
}
q_ji.push(N);
for (int i=2;i<=N-1;++i) {
if (i&1) {
ll num=q_ou.front();
q_ou.pop();
ans_ls[i]=num;
}else {
ll num=q_ji.front();
q_ji.pop();
ans_ls[i]=num;
}
}
}else {
/*
4 1 5 | 2 6 3
6 一共输出了 1 个序列
*/
// if (N==6) {
// cout<<"4 1 5 2 6 3\n";
// return;
// }
auto mirror_assign=[&](ll i) {
ans_ls[N+1-i]=N+1-ans_ls[i];
};
if (N%4!=0) {
ans_ls[1]=N-2;
ans_ls[N]=3;
ans_ls[N-1]=N;
ans_ls[2]=1;
ans_ls[3]=N-1;
ans_ls[N-2]=N+1-ans_ls[3];
ll cnt=1;
vector<array<ll,2>> num_ls(N/2+2);
ll idx=1;
for (int i=4;i<=N;i+=2) {
num_ls[idx]={i,i+1};
++idx;
}
for (int i=4;i<=N/2;i+=2) {
if (cnt&1) {
ans_ls[i]=num_ls[cnt+1][0];
ans_ls[i+1]=num_ls[cnt+1][1];
}else{
ans_ls[i]=num_ls[cnt-1][0];
ans_ls[i+1]=num_ls[cnt-1][1];
}
mirror_assign(i);
mirror_assign(i+1);
++cnt;
}
}else {
/*
10 5 4 12 2 7 | 6 11 1 9 8 3
12 一共输出了 2 个序列
18 5 4 20 2 7 6 9 8 11 | 10 13 12 15 14 19 1 17 16 3
26 5 4 28 2 7 6 9 8 11 10 13 12 15 14 17 16 19 18 21 20 23 22 27 1 25 24 3
WA:22 5 4 24 2 7 6 9 8 11 10 13 | 12 15 14 17 16 19 18 23 1 21 20 3
*/
ans_ls[1]=N-2;
mirror_assign(1);
ans_ls[2]=5;
mirror_assign(2);
ans_ls[3]=4;
mirror_assign(3);
ans_ls[4]=N;
mirror_assign(4);
ans_ls[5]=2;
mirror_assign(5);
ans_ls[6]=7;
mirror_assign(6);
ll cnt=6;
for (int i=7;i<=N/2;i+=2) {
ans_ls[i]=cnt;
mirror_assign(i);
ans_ls[i+1]=cnt+3;
mirror_assign(i+1);
cnt+=2;
}
ll lb=lowbit(N);
if (lb>=8) {
swap(ans_ls[4],ans_ls[8]);
}
if (lb>8) {
swap(ans_ls[8],ans_ls[lb]);
}
}
}
// #undef LOCAL
#ifndef LOCAL
for (int i=1;i<=N;++i) {
cout<<ans_ls[i]<<" ";
}
cout<<"\n";
#else
bool ok_zong=true;
for (int i=1;i<=N-1;++i) {
bool ok=false;
for (int j=i;j<=N;++j) {
if ((ans_ls[j]^(i))==ans_ls[i]) {
ok=true;
break;
}
}
if (!ok) {
ok_zong=false;
break;
}
}
if (ok_zong) {
for (int i=1;i<=N;++i) {
cout<<ans_ls[i]<<" ";
}
cout<<"\n";
return;
}
cout<<"WA:";
for (int i=1;i<=N;++i) {
cout<<ans_ls[i]<<" ";
if (i==N/2) {
cout<<"| ";
}
}
cout<<"\n";
#endif
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2189/submission/359512601
*/
```
:::
::: 打表程序
```cpp
/**
* Problem: ${PROBLEM_NAME}
* Contest: ${PROBLEM_GROUP_NAME}
* Judge: ${ONLINE_JUDGE_NAME}
* URL: ${PROBLEM_URL}
* Created: 2026-01-24 10:48:47
* Author: Gospel_rock
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
void Solve() {
ll N;
cin >> N;
vector<char> used(N+2);
vector<ll> P(N+2);
ll cnt=0;
auto dfs=[&](auto && self,ll idx) {
if (idx==N) {
++cnt;
P[N]=3;
for (int i=1;i<=N;++i) {
cout<<P[i]<<" ";
if (i==N/2) cout<<"| ";
}
cout<<"\n";
return;
}
if (idx<=N/2) {
for (int v=1;v<=N;++v) {
if (idx==1 && v!=N-2) continue;
// if (idx>N/2 && v!=N+1-P[N+1-idx]) continue;
if (used[v]) continue;
ll target=v^idx;
if (target>=1 && target<=N && !used[target]) {
used[v]=true;
P[idx]=v;
self(self,idx+1);
used[v]=false;
}
}
}else {
for (int v=N+1-P[N+1-idx];v<=N+1-P[N+1-idx];++v) {
if (used[v]) continue;
ll target=v^idx;
if (target>=1 && target<=N && !used[target]) {
used[v]=true;
P[idx]=v;
self(self,idx+1);
used[v]=false;
}
}
}
};
dfs(dfs,1);
cout<<N<<" "<<"一共输出了 "<<cnt<<" 个序列\n";
cout<<"\n---------------------------------\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> lT;
while(lT--)
Solve();
return 0;
}
/*
*/
```
:::
## 心路历程（WA，TLE，MLE……）