agc031 C Differ by 1 Bit

転送ゲート:https://atcoder.jp/contests/agc031/tasks/agc031_c
問題:
x x x or yを考えると、問題は0->x x or yから
2 n−1 2^n−1 2 n−1は奇数であるため,すべてのx x o r y x~xor~y x or yに偶数個の1無解がある.
我々が任意に下位を交換することは関係ないので,000…−>111(k(k奇数)個1)00…,000…−>111(k奇数)個1)00…,000…−>111(k奇数)個1)00…,000…−>111(k奇数)個1)00…,000…,000…−
s(n,k)s(n,k)s(n,k)s(n,k)はk個の1がある場合の答えを表す.
k=1の時、明らかにあります:強制第1位は0で、後ろは任意に歩き終わって、n-1、kの任意の情況を通じて押してそれから第1位を1に変えて、後ろの逆さまに歩いて後ろの全0に戻ることができます
k>=3の場合
1位を0に固定することを考慮して,s(n−1,k−2)s(n−1,k−2)s(n−1,k−2)s(n−1,k−2)s
1位を1に変更して、今后の位を全0(歩く时は异なります)と見なして、s(n-1,1)を歩いて、1の位置がn-k+1のところに移ることに注意します.

#include
#include
#include
#include
#include
#define ll long long
#define db double
#define ld long double
#define pp printf
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define pb push_back
#define sz size()
using namespace std;

vector<int> a[18][18];


int z[1 << 18];
int us[20], to[20];

void zh(int x, int y, int n) {
	ff(i, 0, n) us[i] = 0;
	ff(i, 0, n) {
		ff(j, 0, n) if((x >> i & 1) == (y >> j & 1) && !us[j])
			{ us[j] = 1; to[i] = j; break;}
	}
	ff(i, 0, 1 << n) {
		int s = 0;
		ff(j, 0, n) s += (i >> j & 1) * (1 << to[j]);
		z[i] = s;
	}
}

int n, x, y, c;

void pr(int x, int n) {
	fd(i, n - 1, 0) pp("%d", x >> i & 1); pp(" ");
}

int main() {
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
	n = 17;
	a[1][1].pb(0); a[1][1].pb(1);
	fo(i, 2, n) {
		int mx = 1 << (i - 1);
		ff(k, 0, a[i - 1][1].sz)
			a[i][1].pb(a[i - 1][1][k]);
		fd(k, a[i - 1][1].sz - 1, 0)
			a[i][1].pb(a[i - 1][1][k] + mx);
			
		for(int j = 3; j <= i; j += 2) {
			ff(k, 0, a[i - 1][j - 2].sz)
				a[i][j].pb(a[i - 1][j - 2][k]);
			int h = a[i - 1][j - 2][a[i - 1][j - 2].sz - 1];
			zh(1 << (i - 2), 1 << (i - j), i - 1);
			ff(k, 0, a[i - 1][1].sz)
				a[i][j].pb((z[a[i - 1][1][k]] ^ h) + (1 << (i - 1)));
		}
	}
	scanf("%d %d %d", &n, &x, &y);
	ff(i, 0, n) c += (x ^ y) >> i & 1;
	if(c % 2 == 0) {
		pp("NO
"); return 0;
	}
	pp("YES
");
	zh(a[n][c][a[n][c].sz - 1], x ^ y, n);
	ff(k, 0, a[n][c].sz) pp("%d ", z[a[n][c][k]] ^ x);
	
}