CF1325D Ehab the Xorcist 题解

题目链接：CF1325D Ehab the Xorcist

题意：

给定整数 \(u\) 和 \(v(0\le u,v \le 10^{18})\)

试构造长度最短的数组，使得数组内所有元素的异或和为 \(u\)，加和为 \(v\)。

如果有解，输出两行，第一行输出一个整数 \(n\)，第二行输出 \(n\) 个非负整数，表示数组里的元素。

多解输出任意一组即可。如果无解，输出一行一个整数 \(-1\)。

Codeforces 居然没有 C++14 的提交方式了。

简单观察样例可以发现结论， \(u > v\) 时一定无解。

这点很容易证明，因为异或本质上是二进制下的不进位加法，所以无论如何值都不会变得更大。

根据上面的结论，可以发现 \[ a + b = (a\oplus b) + 2(a \land b) \] 即 \[ a + b - (a\oplus b) = 2(a \land b) \] 这里的 \((a\land b)\times 2\) 表示的是手动进位（因为异或是不进位加法）

当然这里还有一个附加的结论，即 \(\left(\sum_i x_i - \bigoplus_i x_i\right)\) 的值一定为偶数。

记 \(\Delta = v - u\) ，则一般情况下 \(\Delta\) 可以拆分为 \(\{\frac{\Delta}{2},\frac{\Delta}{2}\}\) ，也就是说 \(\{\frac{\Delta}{2},\frac{\Delta}{2},u\}\) 是一个一般可行解。

那什么时候不是可行解呢？其实就是一些特殊情况：

• \(\Delta = 0\,\land\,u = v \ne 0\) ，此时解为 \(\{u\}\) 。
• \(\Delta = 0 \,\land \,u = v = 0\) ，此时解为 \(\varnothing\) 。
• \((u \land \frac{\Delta}{2}) = 0\) ，此时我们可以直接以 \(u \oplus \frac{\Delta}{2}\) 合并，即解为 \(\{\frac{\Delta}{2},\frac{\Delta}{2} \oplus u\}\) 。

时间复杂度 \(\mathcal{O}(1)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int u,v; cin >> u >> v;
    int d = v - u;
    if(d < 0 || (d & 1)) return cout << "-1\n", 0;
    if(d == 0) { u ? (cout << "1\n" << u) : (cout << '0'); cout << '\n'; }
    else {
        int x = d >> 1;
        if((x & u) == 0) cout << "2\n" << x << ' ' << (x ^ u) << '\n';
        else cout << "3\n" << x << ' ' << x << ' ' << u << '\n';
    }
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/syksykCCC/solution-cf1325d

---

年代久远的图：