Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)——CF-2211-D. AND-array

题目大意

题目描述

对于一个长度为 $n$ 的未知序列 $a$，定义其 AND-数组 $f(a)$ 如下：

$f(a)k = \sum{1 \le i_1 < i_2 < \dots < i_k \le n} a_{i_1} \mathbin{\&} a_{i_2} \mathbin{\&} \dots \mathbin{\&} a_{i_k}$

其中 $1 \le k \le n$，$\mathbin{\&}$ 表示按位与操作。换句话说，$f(a)_k$ 是序列 $a$ 中所有长度为 $k$ 的子序列的按位与结果之和。

现在给定一个长度为 $n$ 的序列 $b$，满足对于所有的 $1 \le i \le n$，都有 $b_i \equiv f(a)_i \pmod{10^9+7}$。

请根据给定的序列 $b$，构造并输出任意一个满足条件的序列 $a$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例包含两行：
第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示序列 $a$ 和 $b$ 的长度。
第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$0 \le b_i < 10^9+7$），表示序列 $b$。

保证存在长度为 $n$ 且满足 $0 \le a_i < 2^{29}$ 的序列 $a$ 使得条件成立。
保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i < 2^{29}$），表示重构出的序列 $a$。如果有多个满足条件的序列，输出任意一个即可。

样例输入

3
3
0 0 0
5
22 24 10 1 0
10
130 585 1560 2730 3276 2730 1560 585 130 13

样例输出

0 0 0
5 3 6 1 7
13 13 13 13 13 13 13 13 13 13

样例解释

在第二个样例中，若构造的序列 $a = [5, 3, 6, 1, 7]$，其 $f(a)_4$ 的值为：
$(a_1 \mathbin{\&} a_2 \mathbin{\&} a_3 \mathbin{\&} a_4) + (a_1 \mathbin{\&} a_2 \mathbin{\&} a_3 \mathbin{\&} a_5) + (a_1 \mathbin{\&} a_2 \mathbin{\&} a_4 \mathbin{\&} a_5) + (a_1 \mathbin{\&} a_3 \mathbin{\&} a_4 \mathbin{\&} a_5) + (a_2 \mathbin{\&} a_3 \mathbin{\&} a_4 \mathbin{\&} a_5) = 0 + 0 + 1 + 0 + 0 = 1$。
且 $f(a)_1 = a_1 + a_2 + a_3 + a_4 + a_5 = 22$。可以证明对于所有 $1 \le i \le 5$ 均有 $f(a)_i = b_i$，因此 $a = [5, 3, 6, 1, 7]$ 是一个合法的解。

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）