CF-1075-C2. XOR-convenience (Hard Version)（打表，错误的时候可以输出错误的地方）（如果说已经构造出来了简单版，复杂版可能也只需要微调）

题目大意

题目总结

问题描述

给定一个正整数 $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 的话，其实只需要增加一行代码：

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

源代码（构造）

/**
 * 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

源代码（打表找规律）

/**
 * 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

*/

打表程序

/**
 * 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……）