103654: [Atcoder]ABC365 E - Xor Sigma Problem
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：14
Solved：0
Description
Score : $450$ points
Problem Statement
You are given an integer sequence $A=(A_1,\ldots,A_N)$ of length $N$. Find the value of the following expression:
$\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N (A_i \oplus A_{i+1}\oplus \ldots \oplus A_j)$.Notes on bitwise XOR
The bitwise XOR of non-negative integers $A$ and $B$, denoted as $A \oplus B$, is defined as follows:- In the binary representation of $A \oplus B$, the digit at the $2^k$ ($k \geq 0$) position is $1$ if and only if exactly one of the digits at the $2^k$ position in the binary representations of $A$ and $B$ is $1$; otherwise, it is $0$.
In general, the bitwise XOR of $k$ integers $p_1, \dots, p_k$ is defined as $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$. It can be proved that this is independent of the order of $p_1, \dots, p_k$.
Constraints
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^8$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$
$A_1$ $A_2$ $\ldots$ $A_{N}$
Output
Print the answer.
Sample Input 1
3 1 3 2
Sample Output 1
3
$A_1 \oplus A_2 = 2$, $A_1 \oplus A_2 \oplus A_3 = 0$, and $A_2 \oplus A_3 = 1$, so the answer is $2 + 0 + 1 = 3$.
Sample Input 2
7 2 5 6 5 2 1 7
Sample Output 2
83
Output
得分：450分
问题陈述
给定一个长度为$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。
一般来说，$k$个整数$p_1, \dots, p_k$的按位异或是$(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \ldots \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