Xor 西格玛问题

题目描述

给定长度为 $N$ 的整数序列 $A=(A_1,\ldots,A_N)$。求下列表达式的值：

$\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N (A_i \oplus A_{i+1}\oplus \ldots \oplus A_j)$。

关于按位异或的说明

非负整数 $A$ 和 $B$ 的按位异或 $A \oplus B$ 定义如下：

在 $A \oplus B$ 的二进制表示中，第 $2^k$（$k \geq 0$）位的数字为 $1$，当且仅当 $A$ 和 $B$ 的二进制表示中第 $2^k$ 位的数字恰好有一个是 $1$；否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制：$011 \oplus 101 = 110$）。

一般来说，$k$ 个整数 $p_1, \dots, p_k$ 的按位异或定义为 $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$。可以证明这个结果与 $p_1, \dots, p_k$ 的顺序无关。

输入格式

输入按以下格式从标准输入给出。

$N$
$A_1$ $A_2$ $\ldots$ $A_{N}$

输出格式

输出答案。

样例

3
1 3 2

3

$A_1 \oplus A_2 = 2$，$A_1 \oplus A_2 \oplus A_3 = 0$，$A_2 \oplus A_3 = 1$，所以答案是 $2 + 0 + 1 = 3$。

7
2 5 6 5 2 1 7

83

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^8$
• 所有输入值均为整数