题解 | #Prime XOR Permutation#

题意

构造一个 的排列，使得相邻两个数异或起来是质数。

思路

爆搜。

实现

#include<bits/stdc++.h>
#define up(a,b,c)for(int a=b;a<=c;++a)
#define dn(a,b,c)for(int a=b;a>=c;--a)
const int N=22e5;
using namespace std;
int T,n,np[N];
vector<int>qwq,ans;
bool dfs(){
        if(qwq.empty())return 1;
        int sz=int(qwq.size());
        dn(i,int(qwq.size())-1,0){
                if(ans.empty()||!np[ans.back()^qwq[i]]){
                        int x=qwq[i];
                        qwq.erase(qwq.begin()+i),ans.push_back(x);
                        if(dfs())return 1;
                        qwq.insert(qwq.begin()+i,x),ans.pop_back();
                }
        }
        return 0;
}
int main(){
        cin.tie(0)->sync_with_stdio(0);
        cin>>T;
        while(T--){
                cin>>n;
                np[1]=1;
                up(i,1,n*2)
                        if(!np[i])
                                up(j,2,n*2/i)
                                        np[i*j]=1;
                qwq.clear(),ans.clear();
                up(i,0,n-1)qwq.push_back(i);
                if(dfs()){
                        up(i,0,n-1)cout<<ans[i]<<' ';cout<<'\n';
                }else cout<<"-1\n";
        }
        return 0;
}