8339: 洛谷P9227 - 异或积
[Creator : ]
Description
# 题目背景
$\texttt{id: 4d7e}$
小 H 在课堂上学习了异或运算。
对于两个非负整数 $x,y$，它们的**异或**是指，将它们作为二进制数，对二进制表示中的每一位进行如下运算得到的结果：
- $x$ 和 $y$ 的这一位上不同时，结果的这一位为 $1$；
- $x$ 和 $y$ 的这一位上相同时，结果的这一位为 $0$。
$x$ 和 $y$ 的异或被记为 $x \operatorname{xor} y$ 或 $x \oplus y$。
在 C++ 中，你可以用 `x ^ y` 得到 $x$ 与 $y$ 的异或值。
另外，若干个数的异或称之为**异或和**。
# 题目描述
小 H 还了解到，一个长度为 $n$ 的数列 $a$ 的**异或积**是一个等长的数列 $b$，其中 $b_i$ 等于数列 $a$ 中除了 $a_i$ 以外其他元素的异或和，即
$b_i = \bigoplus \limits_{j = 1}^{n} [j\ne i] a_j$
例如，数列 $\{1, 2, 3, 4\}$ 的异或积为 $\{5, 6, 7, 0\}$。
异或积变换 是指将一个数列用它的异或积替换的过程，由于异或积变换之后数列长度不变，所以异或积变换可以连续进行多次。
现在，小 H 有一个长度为 $n$ 的数列 $a$，他想请你帮他计算出 $a$ 经过 $k$ 次异或积变换之后得到的序列。
$\texttt{id: 4d7e}$
小 H 在课堂上学习了异或运算。
对于两个非负整数 $x,y$，它们的**异或**是指，将它们作为二进制数，对二进制表示中的每一位进行如下运算得到的结果：
- $x$ 和 $y$ 的这一位上不同时，结果的这一位为 $1$；
- $x$ 和 $y$ 的这一位上相同时，结果的这一位为 $0$。
$x$ 和 $y$ 的异或被记为 $x \operatorname{xor} y$ 或 $x \oplus y$。
在 C++ 中，你可以用 `x ^ y` 得到 $x$ 与 $y$ 的异或值。
另外，若干个数的异或称之为**异或和**。
# 题目描述
小 H 还了解到，一个长度为 $n$ 的数列 $a$ 的**异或积**是一个等长的数列 $b$，其中 $b_i$ 等于数列 $a$ 中除了 $a_i$ 以外其他元素的异或和，即
$b_i = \bigoplus \limits_{j = 1}^{n} [j\ne i] a_j$
例如，数列 $\{1, 2, 3, 4\}$ 的异或积为 $\{5, 6, 7, 0\}$。
异或积变换 是指将一个数列用它的异或积替换的过程，由于异或积变换之后数列长度不变，所以异或积变换可以连续进行多次。
现在，小 H 有一个长度为 $n$ 的数列 $a$，他想请你帮他计算出 $a$ 经过 $k$ 次异或积变换之后得到的序列。
Input
**本题单个测试点内有多组测试数据**。
第一行一个整数 $T$，表示测试数据组数。
对于每一组测试数据：
第一行两个整数 $n,k$。
第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。
第一行一个整数 $T$，表示测试数据组数。
对于每一组测试数据：
第一行两个整数 $n,k$。
第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。
Output
对于每一组测试数据：
一行 $n$ 个整数，表示数列 $a$ 经过 $k$ 次异或积变换之后得到的数列。
一行 $n$ 个整数，表示数列 $a$ 经过 $k$ 次异或积变换之后得到的数列。
Constraints
对于 $100\%$ 的测试数据，$1 \le T \le 10$，$2 \le n \le 10^5$，$1 \le k \le 10^{18}$，$0 \le a_i < 2^{32}$。
|
测试点编号 |
$n\leq$ |
$k \leq$ |
特殊性质 |
|
$1 \sim 3$ |
$100$ |
$100$ |
|
|
$4 \sim 5$ |
$1000$ |
$1000$ |
|
|
$6 \sim 7$ |
$3$ |
$10^{18}$ |
|
|
$8 \sim 10$ |
$10^5$ |
$3$ |
|
|
$11 \sim 13$ |
$10^5$ |
$10^{18}$ |
$a$ 中所有数的异或和为 $0$ |
|
$14 \sim 15$ |
$10^5$ |
$10^{18}$ |
$n$ 为奇数 |
|
$16 \sim 17$ |
$10^5$ |
$10^{18}$ |
$n$ 为奇数 |
|
$18 \sim 20$ |
$10^5$ |
$10^{18}$ |
|
Sample 1 Input
1
4 1
1 2 3 4
Sample 1 Output
5 6 7 0
Sample 2 Input
1
4 2
0 0 0 1
Sample 2 Output
0 0 0 1
第 $1$ 次异或积变换：$\{0,0,0,1\}\to\{1,1,1,0\}$；
第 $2$ 次异或积变换：$\{1,1,1,0\}\to\{0,0,0,1\}$。
第 $2$ 次异或积变换：$\{1,1,1,0\}\to\{0,0,0,1\}$。