6374. 异或和与和
时间限制：1000 MS 内存限制：512 MB
题目描述
## 题目描述 给你一个长度为 $n$ 的数组 $a$，求它所有非空子序列的异或和之和。 例如 $a=[1,2,3]$ 有七个非空子序列：$[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]$，它们的异或和分别为 $1,2,3,3,2,1,0$。因此，所有非空子序列的异或和之和为 $1+2+3+3+2+1+0=12$。 由于答案可能非常大，你需要输出答案对 $10^9+7$ 取模后的结果。 ## 输入格式 第一行输入一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。 第二行输入 $n$ 个整数，表示数组 $a$ 中的元素 $a\_1, a\_2, \dots, a\_n$（$0 \le a\_i \le 10^9$）。 ## 输出格式 输出一个整数，表示 $a$ 的所有非空子序列的异或和之和对 $10^9+7$ 取模后的结果。 ## 输入输出样例 ### 输入样例 1 ``` 3 1 2 3 ``` ### 输出样例 1 ``` 12 ``` ## 提示/说明 ### 样例 1 解释 数组 $a = [1, 2, 3]$ 的所有非空子序列及对应的异或和如下： - `[1]`：异或和为 $1$ - `[2]`：异或和为 $2$ - `[3]`：异或和为 $3$ - `[1, 2]`：异或和为 $1 \oplus 2 = 3$ - `[1, 3]`：异或和为 $1 \oplus 3 = 2$ - `[2, 3]`：异或和为 $2 \oplus 3 = 1$ - `[1, 2, 3]`：异或和为 $1 \oplus 2 \oplus 3 = 0$ 将这些异或和相加，得到 $1+2+3+3+2+1+0 = 12$。对 $10^9+7$ 取模后仍为 $12$。 ### 数据规模与约定 对于所有数据，保证： - $1 \le n \le 2 \cdot 10^5$； - $0 \le a\_i \le 10^9$。