『STA - R7』异或生成序列
题目描述
对于一个 $1 \sim n$ 的排列 $\{p_n\}$,定义其异或生成序列为一个长度为 $n - 1$ 的非负整数序列 $\{b_{n - 1}\}$,按如下方式生成:
$$b_i = p_i \operatorname{xor} p_{i + 1}$$
其中 $\operatorname{xor}$ 代表按位异或运算。在 C++ 语言中由 `^` 运算符表示。
给定 $n, \{b_{n - 1}\}$,你需要构造一个对应的排列 $\{p_n\}$。
输入数据保证有解,如果存在多个解,输出任意一个即可。
输入输出格式
输入格式
**本题单个测试点内含有多组测试数据。**
第一行一个正整数 $T$,代表测试数据组数。
对于每组测试数据,
- 第一行一个正整数 $n$。
- 第二行 $n - 1$ 个非负整数,代表异或生成序列 $\{b_{n - 1}\}$。
输出格式
对于每组测试数据,输出一行 $n$ 个正整数,代表一个对应的排列 $\{p_n\}$。如果存在多个解,输出任意一个即可。
输入输出样例
输入样例 #1
2
4
1 2 5
6
1 7 3 2 5
输出样例 #1
2 3 1 4
3 2 5 6 4 1
说明
**【样例解释】**
对于第一组测试数据,我们有:
- $b_1 = p_1 \operatorname{xor} p_2 = 2 \operatorname{xor} 3 = 1$
- $b_2 = p_2 \operatorname{xor} p_3 = 3 \operatorname{xor} 1 = 2$
- $b_3 = p_3 \operatorname{xor} p_4 = 1 \operatorname{xor} 4 = 5$
因此得到的 $b$ 序列和输入中的相同,进而该排列符合要求。
对于第二组测试数据,$[4,5,2,1,3,6]$ 也是一个符合要求的排列。
**【数据范围】**
**本题采用捆绑测试。**
对于 $100\%$ 的数据:
- $2 \le n \le 2 \times 10^6$;
- $1 \le T \le 10^6$;
- $\sum n \le 2 \times 10^6$;
- 保证至少存在一个合法的解。
具体部分分分配如下:
|Subtask 编号|数据范围|分值|
|:--------:|:--------:|:--------:|
|1|$\sum n^2 \le 2 \times 10^6$|$17$|
|2|$2 \nmid n$|$23$|
|3|$4 \mid n$|$26$|
|4|无特殊限制|$34$|
**【提示】**
本题输入文件较大,请使用较为快速的输入方式。