D. XOR Construction
You are given $n-1$ integers $a_1, a_2, \dots, a_{n-1}$.
Your task is to construct an array $b_1, b_2, \dots, b_n$ such that:
- every integer from $0$ to $n-1$ appears in $b$ exactly once;
- for every $i$ from $1$ to $n-1$, $b_i \oplus b_{i+1} = a_i$ (where $\oplus$ denotes the bitwise XOR operator).
Input
The first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$).
The second line contains $n-1$ integers $a_1, a_2, \dots, a_{n-1}$ ($0 \le a_i \le 2n$).
Additional constraint on the input: it's always possible to construct at least one valid array $b$ from the given sequence $a$.
Output
Print $n$ integers $b_1, b_2, \dots, b_n$. If there are multiple such arrays, you may print any of them.
Examples
input
4
2 1 2output
0 2 3 1 input
6
1 6 1 4 1output
2 3 5 4 0 1
解题思路
我的做法跟官方的基本一样。最关键的地方是要观察出 $a$ 其实就是 $b$ 的差分数组，假设下标都从 $0$ 开始，即有 $b_i = b_0 \oplus a_0 \oplus a_1 \oplus \cdots \oplus a_{i-1}$。主要是如果看到有 $a_i = b_i - b_{i-1}$ 或者 $a_i = b_i \oplus b_{i-1}$ 就要想到对 $a$ 求前缀和就会得到 $b$。
然而我们现在还不知到 $b_0$，假设 $c_0 = 0$，$c_i = a_0 \oplus \cdots \oplus a_{i-1}, \, (i \geq 1)$，如果知道 $b_0$ 的话那么整个 $b$ 数组都确定下来了，就是 $b_0$ 异或每个 $c_i$。所以很自然想到枚举 $0 \sim n-1$ 来找到合法 $b_0$，使得 $b_0$ 与每个 $b_0 \oplus c_i$ 恰好是 $0 \sim n-1$ 的全排列。如果直接暴力验证的话时间复杂度就是 $O(n^2)$，注意到题目保证存在解，所以可以分析一下 $c_i$ 具有什么性质。
首先 $c_i$ 一定是成对不同的，否则假设 $c_i = c_j$，那么不管 $b_0$ 取什么必然有 $c_i \oplus b_0 = c_j \oplus b_0$，因此不可能存在解，矛盾。由于 $c_i$ 成对不同的，意味着 $c_i \oplus b_0$ 也是成对不同的，所以如果 $\max\limits_{0 \leq i \leq n-1}\{ c_i \oplus b_0 \} < n$，那么此时 $c_i \oplus b_0$ 一定是 $0 \sim n-1$ 的全排列，此时的 $b_0$ 就是合法的解。
为了快速得到 $b_0$ 与这些 $c_i$ 异或后的最大值是多少，可以将 $c_i$ 存到 trie 中，然后从最高位开始贪心选择即可。
AC 代码如下，时间复杂度为 $O(n \log{n})$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int a[N];
int tr[N * 19][2], idx;
void add(int x) {
int p = 0;
for (int i = 18; i >= 0; i--) {
int t = x >> i & 1;
if (!tr[p][t]) tr[p][t] = ++idx;
p = tr[p][t];
}
}
int query(int x) {
int p = 0, ret = 0;
for (int i = 18; i >= 0; i--) {
int t = x >> i & 1;
if (tr[p][!t]) {
p = tr[p][!t];
ret |= 1 << i;
}
else {
p = tr[p][t];
}
}
return ret;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int x;
scanf("%d", &x);
a[i] = a[i - 1] ^ x;
add(a[i]);
}
add(0);
for (int i = 0; i < n; i++) {
if (query(i) < n) {
for (int j = 0; j < n; j++) {
printf("%d ", a[j] ^ i);
}
break;
}
}
return 0;
}再提供另外一种思路，按位考虑每一个 $c_i$。对于二进制的第 $k$ 位，如果每个 $c_i$ 的第 $k$ 位共有 $x$ 个 $1$，数字 $0 \sim n-1$ 的第 $k$ 位共有 $y$ 个 $1$，由于题目保证有解，因此如果 $x \ne y$，那么只需让 $b_0$ 的第 $k$ 位为 $1$ 即可，否则为 $0$。
AC 代码如下，时间复杂度为 $O(n \log{n})$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int a[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int x;
scanf("%d", &x);
a[i] = a[i - 1] ^ x;
}
int ret = 0;
for (int i = 0; i <= 18; i++) {
int s = 0;
for (int j = 0; j < n; j++) {
s += j >> i & 1;
s -= a[j] >> i & 1;
}
if (s) ret |= 1 << i;
}
for (int i = 0; i < n; i++) {
printf("%d ", a[i] ^ ret);
}
return 0;
}
参考资料
Educational Codeforces Round 157 Editorial：https://codeforces.com/blog/entry/122034
Educational Codeforces Round 157 (Rated for Div. 2)：https://zhuanlan.zhihu.com/p/665022975