CF2211D AND-array

对于长度为 $n$ 的序列 $a$，我们定义其 AND-数组 $f(a)$ 如下： $$ f(a)_k = \sum\limits_{1 \le i_1 < i_2 < \ldots < i_k \le n} a_{i_1} \& a_{i_2} \& \ldots \& a_{i_k} $$ 对于所有 $1\le k\le n$，其中 $\&$ 表示[按位与运算](https://en.wikipedia.org/wiki/Bitwise_operation#AND)。 换句话说，$f(a)_k$ 是对 $a$ 的所有长度为 $k$ 的子序列按位与后的和。 你并不知道序列 $a$，但你给定了一个长度为 $n$ 的序列 $b$，满足对于所有 $1 \le i \le n$ 都有 $b_i \equiv f(a)_i \pmod{10^9 + 7}$。根据给定序列 $b$ 请你还原出原始序列 $a$。 $^\ast$ 序列 $c$ 是序列 $d$ 的子序列，指的是 $c$ 可以通过从 $d$ 中删除若干（可能为零或全部）元素并保留原有顺序得到。如果删除元素的位置不同，则认为子序列不同。

每组测试数据包含多个测试用例。首行为测试用例数量 $t$（$1 \le t \le 10^4$）。每个测试用例描述如下： 每个测试用例第一行包含一个整数 $n$（$1 \le n \le 10^5$）——序列 $a$ 和 $b$ 的长度。 第二行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$0 \le b_i < 10^9 + 7$）——序列 $b$。 保证存在长度为 $n$、$0 \le a_i < 2^{29}$ 的序列 $a$，使得对于所有 $1 \le i \le n$，都有 $b_i \equiv f(a)_i \pmod{10^9 + 7}$。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i < 2^{29}$），表示还原出的序列 $a$。如果有多组满足要求的解，可以输出任意一组。

在第二个样例中，对于 $a = [5, 3, 6, 1, 7]$，有 $f(a)_4 = a_1 \& a_2 \& a_3 \& a_4 + a_1 \& a_2 \& a_3 \& a_5 + a_1 \& a_2 \& a_4 \& a_5 + a_1 \& a_3 \& a_4 \& a_5 + a_2 \& a_3 \& a_4 \& a_5 = 0 + 0 + 1 + 0 + 0 = 1$，$f(a)_1 = a_1 + a_2 + a_3 + a_4 + a_5 = 22$。可以证明 $f(a)_i = b_i$ 对所有 $1 \le i \le 5$ 都成立，因此 $a = [5, 3, 6, 1, 7]$ 是一个合法的解。 由 ChatGPT 5 翻译