前置知识:或运算=俩0为0,否则为1,异或运算=相同为0,不同为1
首先根据或运算性质,x为0的位,数组中每个元素的这一位都必须是0,
既然所有元素携带的1只能落在x为1的位置上,那么它们的异或和y也绝对不可能在x为0的位置上出现1。由此得出:y的二进制必须是x的子集(即 (x & y) == y)不满足这一点,直接NO。
从小规模开始考虑,逐渐分类讨论
1.如果x的二进制中只有一个1:因为所有元素必须大于0,且只能使用x里的这一位1,所以这n个元素必须全部等于 x。
如果n的个数是偶数,那么异或和为0,然而又要求异或和为y(大于0),所以这种情况NO;
如果n个数为奇数,异或和为x,如果x!=y,也是NO
2.如果x二进制中有多个1:依旧从小规模开始思考问题
如果n==1,一个数,必须x==y,否则NO;
如果n==2,想一下,两个数,我们想让a|b==x,a^b==y,由于任何数异或自己等于0,所以有(x^x)^y==y,根据结合律,x^(x^y)==y,所以猜想两个数就是x和x^y;验证得或运算也满足
如果n>=3,由n==2启发,我们可以直接令前n-2个数为x,留下两个数来控制把整个数组的xor和修正为 y,这样就可以回归到n==2的情形,此时前n-2个数的和S根据奇偶性质要么为x要么为0,我们设最后两个数xor和为yy,那么有yy^s==y,即为yy==y^S,这样就完全转化为了n==2的那个情况,求两个数xor和为yy,or和为x,同样进行分类讨论即可。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ui = unsigned;
using ulll = unsigned __int128;
using lll = __int128;
using db = double;
using ldb = long double;
using b20 = bitset<20>;
const int Inf = 0x3f3f3f3f;
const ll Linf = 0x3f3f3f3f3f3f3f3fLL;
const db Dinf = 1e18;
const int Maxm = 400005;
const int Maxn = 10005;
const int MOD[] = {998244353, 1000000007};
#define endl '\n'
//------------------------------------------------------------------
ll lowbit(ll x) {
return x & -x;
}
void solve() {
ll n, x, y;
cin >> n >> x >> y;
if ((x & y) != y) {
cout << "NO\n";
return;
}
if (__builtin_popcountll(x) == 1) {
if (!(n & 1) || x != y) {
cout << "NO\n";
return;
} else {
cout << "YES\n";
while (n--) {
cout << x << ' ';
}
cout << endl;
return;
}
} else {
if (n == 1) {
if (x != y) {
cout << "NO\n";
return;
} else {
cout << "YES\n";
cout << x << endl;
}
} else if (n == 2) {
cout << "YES\n";
if (x == y) {
cout << lowbit(x) << ' ' << (x ^ lowbit(x)) << endl;
return;
} else {
cout << x << ' ' << (x ^ y) << endl;
return;
}
} else {
ll s = ((n - 2) & 1) ? x : 0;
ll yy = s ^ y;
cout << "YES\n";
for (ll i = 1; i <= n - 2; ++i) {
cout << x << ' ';
}
if (yy != x) {
cout << x << ' ' << (x ^ yy) << endl;
return;
} else {
cout << lowbit(x) << ' ' << (x ^ lowbit(x));
cout << endl;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll _;
cin >> _;
while (_--) solve();
return 0;
}

京公网安备 11010502036488号