【普及】异或和

给定长为 $n$ 的数列 $a$，计算和

$$\displaystyle (\sum_{i=1}^{n} \sum_{j=i}^{n} a_i \text{ xor } a_j) \bmod 998244353$$

这里 $\text{ xor }$ 表示按位异或，在 C/C++ 中表示为 ^

什么是 xor 运算？

• $0 \text{ xor } 0 = 0$
• $0 \text{ xor } 1 = 1$
• $1 \text{ xor } 0 = 1$
• $1 \text{ xor } 1 = 0$
• 也就是相同为 0，不同为 1

输入格式

第一行包含 $1$ 个正整数 $n(2 \le n \le 10^5)$

第二行包含 $n$ 个整数表示 $a_i(0 \le a_i \le 2^{31}-1)$

输出格式

对于每组数据输出一行，包含答案

3
0 2 3

6

10
1974282644 2058822687 409093169 609086829 2047366146 1245844157 1653576671 882126195 1527146999 493261995

796037382

提示

【样例 1 解释】

• $0 \text{ xor } 2 = 2$
• $0 \text{ xor } 3 = 3$
• $2 \text{ xor } 3 = 1$
• $2 + 3 + 1 = 6$
• 请注意将最后的答案对 998244353 取模

【数据范围】

• $2 \le n, m \le 10^5$
• $0 \le a_i \le 2^{31}-1$

请思考后再点击查看提示

来源

• 参考答案