官方题解｜添加元素让数组变为好数组

提示

$A \oplus A = 0$

题目解析

任意数字与自己异或的结果为 $0$。

令原数组和为 $sum$，异或和为 $xsum$，那么显然我们可以在数组后添加两个元素：$xsum$ 和 $sum+xsum$。

这样对于添加元素后的数组的和为 $(sum+xsum) \times 2$，异或和为 $sum+xsum$，满足题目要求。

AC代码

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n; cin >> n;
        auto sum = 0LL, xsum = 0LL;
        for (int i = 0; i < n; ++i) {
            int x; cin >> x;
            sum += x;
            xsum ^= x;
        }
        cout << 2 << '\n';
        cout << xsum << ' ' << sum + xsum << '\n';
    }
    return 0;
}

复杂度分析

遍历一遍数组求得 $sum$ 和 $xsum$，时间复杂度 $O(n)$。

---