CF1547D Co-growing Sequence

如果一个非负整数序列 $a_1, a_2, \dots, a_n$ 满足对于所有 $1 \le i \le n-1$，$a_i$ 的二进制表示中所有为 $1$ 的位在 $a_{i+1}$ 的二进制表示中对应位也为 $1$（换句话说，$a_i \:\&\: a_{i+1} = a_i$，其中 $\&$ 表示按位与运算），则称该序列是“增长的”。如果 $n=1$，则该序列也被认为是增长的。 例如，以下四个序列是增长的： - $[2, 3, 15, 175]$ —— 二进制表示为 $[10_2, 11_2, 1111_2, 10101111_2]$； - $[5]$ —— 二进制表示为 $[101_2]$； - $[1, 3, 7, 15]$ —— 二进制表示为 $[1_2, 11_2, 111_2, 1111_2]$； - $[0, 0, 0]$ —— 二进制表示为 $[0_2, 0_2, 0_2]$。 以下三个序列不是增长的： - $[3, 4, 5]$ —— 二进制表示为 $[11_2, 100_2, 101_2]$； - $[5, 4, 3]$ —— 二进制表示为 $[101_2, 100_2, 011_2]$； - $[1, 2, 4, 8]$ —— 二进制表示为 $[0001_2, 0010_2, 0100_2, 1000_2]$。 考虑两个非负整数序列 $x_1, x_2, \dots, x_n$ 和 $y_1, y_2, \dots, y_n$。如果序列 $x_1 \oplus y_1, x_2 \oplus y_2, \dots, x_n \oplus y_n$ 是增长的（其中 $\oplus$ 表示按位异或运算），则称这对序列是“共增长的”。 给定一个整数序列 $x_1, x_2, \dots, x_n$，请你找到字典序最小的序列 $y_1, y_2, \dots, y_n$，使得 $x_i$ 和 $y_i$ 组成的序列是共增长的。 如果存在 $1 \le k \le n$，使得对于任意 $1 \le i < k$ 都有 $a_i = b_i$，但 $a_k < b_k$，则称序列 $a_1, a_2, \dots, a_n$ 的字典序小于 $b_1, b_2, \dots, b_n$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）。接下来有 $t$ 组测试数据。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示序列 $x_i$ 的长度。 第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$0 \le x_i < 2^{30}$），表示序列 $x_i$ 的元素。 保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出 $n$ 个整数 $y_1, y_2, \dots, y_n$（$0 \le y_i < 2^{30}$），表示字典序最小且与给定序列 $x_i$ 共增长的序列。

由 ChatGPT 4.1 翻译