← 返回题目列表

AtCoder · abc365_e

H. 异或西格玛问题

中文机器翻译题面 查看原题

分数: 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.
例如, 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.

约束

  • 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