dalao said 这份代码是有概率保证的。

求计算跑一次正确的概率 qwq

即跑一次 Iamgoodatranding 这个函数。

简要思路就是每次选定随机一位 $s$ 和 $t$ 不同的，然后 $s$ 变为除了这一位其他位都翻转，最后再翻转这一位(即确保 $s$ 和 $t$ 一直在接近)，以后都不动这一位了。

#include<iostream>
#include<algorithm>
#include<vector>
#include<random>
#include<chrono>
#define ll long long
#define sf std::shuffle
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=n;i++)
using namespace std;
const int N=(1<<17)+7;
std::mt19937_64 rd(std::chrono::steady_clock::now().time_since_epoch().count());
int ans[N],tmp[N],answer=0;
int tot=0,n;
void print(int x){
    if(x!=(1<<n)) {cout << "NO\n";return ;}
    cout << "YES\n";
    for(int i=1;i<=x;i++)cout<<ans[i]<<' ';
}
vector <int> have;
void dfs(int x,int &s){
    if(x==have.size())return;
    dfs(x+1,s);
    tmp[++tot]=(s^=(1<<have[x]));
    dfs(x+1,s);
}
void Iamgoodatranding(int s,int t){
    vector <int> temp;
    have.clear();
    for(int i=0;i<n;i++){
        have.pb(i);
    }
    tot=0;
    tmp[++tot]=s;
    while(s!=t){
        temp.clear();
        for(auto i:have)if(((s>>i)&1)!=((t>>i)&1))temp.pb(i);
        int now=temp[rd()%temp.size()];
        for(int i=0;i<have.size();i++)
            if(have[i]==now)have.erase(have.begin()+i);
        sf(have.begin(),have.end(),rd);
        dfs(0,s);
        tmp[++tot]=(s^=(1<<now));
    }
    if(tot>answer){answer=tot;for(int i=1;i<=tot;i++)ans[i]=tmp[i];}
}
signed main(){
    
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int a,b;
    cin>>n>>a>>b;
    double MAX_TIME=1.8;
    while ((double)clock()/CLOCKS_PER_SEC<MAX_TIME) Iamgoodatranding(a,b);
    print(answer);
    return 0;
}