E - Xor Sigma Problem
Editorial
/ 
一般に 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 の順番によらないことが証明できます。
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.
/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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)
ビット単位 xor とは
非負整数 A, B のビット単位 xor 、A \oplus B は、以下のように定義されます。- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 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
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