题解 CF1325D 【Ehab the Xorcist】
syksykCCC
·
·
题解
下面是本文需要用到的几个结论：
> 1. **一个序列的异或和一定小于等于数值和。**
>
> 证明：异或的本质是二进制下的不进位加法，相比起进位的普通加法，所得的结果当然会较小。当然，在进位不会发生，也就是加数之间没有相同的位（与值为 $0$）时，两者是等价的。
>
> 2. **一个序列的数值和和异或和奇偶性相同。**
>
> 证明：首先继续分析结论 1，得到一个等式：
>
> $$ a+b = (a \oplus b) + 2(a \land b)$$
> $$ (a+b) - (a \oplus b) = 2(a \land b) $$
> $2(a \land b)$ 是二进制下手动进位（找到相同位，左移一位）。
>
> 因为 $a \land b$ 一定是整数，所以 $(a+b)-(a \oplus b)$ 一定是 $2$ 的倍数（偶数）。当然，这个只是两个数的情况，三个数或更多依次分析即可。
那么，当 $u \not\equiv v \pmod{2}$，或者 $u > v$ 时，答案就是 $-1$ 了。
记 $\Delta = v - u$。
先考虑一些特殊情况，比如 $\Delta = 0$，也就是 $u = v$，那么数列直接设置为 $[u]$ 就好了。当然，如果恰好 $u=v=0$ 的话，$[]$ 是满足条件的更短的数列。
然后，我们考虑把 $\Delta$ 拆开，让它自相残杀掉，剩下的就只剩一个 $u$ 了。
不要忘了 $\Delta \bmod 2 = 0$，所以我们可以把它分为相等的两个部分，也就是 $[\frac{\Delta}{2},\frac{\Delta}{2}]$，两个相等的数字的异或和一定是等于 $0$ 的。所以，$[\frac{\Delta}{2},\frac{\Delta}{2}, u]$ 就是一个可行的解。
会不会有更优的解呢？我们考虑把 $\frac{\Delta}{2}$ 和 $u$ 合并，如果 $\frac{\Delta}{2} \land u = 0$，那么，我们大可以把它们替换为一个数，即构造 $[\frac{\Delta}{2}, \frac{\Delta}{2} \oplus u]$ 即可，因为它们没有相同位，异或起来不会进位，所以对数值和也没有影响。
```cpp
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
LL u, v;
int main()
{
ios::sync_with_stdio(false);
cin >> u >> v;
LL delta = v - u;
if(delta < 0 || (delta & 1))
{
cout << -1 << endl;
return 0;
}
if(!delta)
{
if(!u) cout << 0 << endl;
else cout << 1 << '\n' << u << endl;
}
else
{
LL haf = delta >> 1;
if((haf & u) == 0) cout << 2 << '\n' << haf << ' ' << (haf ^ u) << endl;
else cout << 3 << '\n' << haf << ' ' << haf << ' ' << u << endl;
}
return 0;
}
```