有点神的构造，考场上想复杂了…

Solution

考虑因为变换 $2^n-1$ 次，那么 $A$ 跟 $B$ 的 $1$ 位数的奇偶性一定不同，用这个来判断是否有解。

通过归纳可以知道如果不同是一定有解的。

假设存在 $n=k$ 的构造方案，考虑如何构造 $k+1$ 位的构造方案。我们可以将 $A$ 和 $B$ 不同的一位（假设是第 $x$ 位）提取出来，剩下 $k$ 位数 $A’$ 和 $B’$ 。他们的位数奇偶性一定相同。那么我们再考虑一个一位与 $A’$ 不同的数 $c$ 。递归去构造一个 $A’\rightarrow c \rightarrow B’$ 的方案。其中前半部分的第 $x$ 位与 $A$ 相同，后半部分与 $B$ 相同。

递归构造即可。

Code

// Code by ajcxsu
// Problem: C

#include<bits/stdc++.h>
using namespace std;

typedef bitset<10> bs;
void solve(int k, int a, int b, vector<int> &op) {
    if(k==1) { op.push_back(a), op.push_back(b); return; }
    int c=0;
    vector<int> L, R;
    for(; ((1<<c)&a)==((1<<c)&b); c++);
    int na=(a&((1<<c)-1))|((a&((1<<k)-1-((1<<c+1)-1)))>>1);
    int nb=(b&((1<<c)-1))|((b&((1<<k)-1-((1<<c+1)-1)))>>1);
    solve(k-1, na, na^1, L);
    solve(k-1, na^1, nb, R);
    for(int x:L) op.push_back(((x&((1<<c)-1))|((x&((1<<(k-1))-1-((1<<c)-1)))<<1))|((1<<c)&a));
    for(int x:R) op.push_back(((x&((1<<c)-1))|((x&((1<<(k-1))-1-((1<<c)-1)))<<1))|((1<<c)&b));
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, a, b;
    cin>>n>>a>>b;
    if(!((__builtin_popcount(a)+__builtin_popcount(b))&1)) cout<<"NO\n", exit(0);
    vector<int> ans;
    solve(n, a, b, ans);
    cout<<"YES\n";
    for(int x:ans) cout<<x<<' ';
    cout<<endl;
    return 0;
}