分数: 450 点
问题陈述
给你一个整数序列 给出了 A=(A_1,\ldots,A_N) 长度 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 当且仅当正好是位于的数字之一 2^k 在二进制表示中的位置 A 和 B is 1;否则,就是 0.
一般来说,按位异或 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.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^8
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 \ldots A_{N}
输出
打印答案。
示例输入 1
3 1 3 2
示例输出 1
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.
示例输入 2
7 2 5 6 5 2 1 7
示例输出 2
83