/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
非負整数列 A = (A_1, \ldots, A_N) が与えられます。 あなたは次の操作を、何度でも行うことができます（一度も行わなくてもよいです）。
- 非負整数 x\in \{A_1,\ldots,A_N\} をひとつ選ぶ。
- すべての i に対して、A_i を A_i\oplus x に置き換える（\oplus はビット単位 \mathrm{XOR} 演算を表します）。
操作後の \sum_{i=1}^N A_i としてありうる最大値を求めてください。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
制約
- 1\leq N \leq 3\times 10^{5}
- 0\leq A_i < 2^{30}
入力
入力は以下の形式で標準入力から与えられます。
N A_1 \ldots A_N
出力
操作後の \sum_{i=1}^N A_i としてありうる最大値を出力してください。
入力例 1
5 1 2 3 4 5
出力例 1
19
例えば次のように操作を行うことで、\sum_{i=1}^N A_i を 19 にすることが可能です。
- はじめ、数列 A は次の状態です：(1,2,3,4,5)。
- x = 1 として操作を行うと、数列 A は次の状態に変化します：(0,3,2,5,4)。
- x = 5 として操作を行うと、数列 A は次の状態に変化します：(5,6,7,0,1)。このとき \sum_{i=1}^N A_i = 5 + 6 + 7 + 0 + 1 = 19 です。
入力例 2
5 10 10 10 10 10
出力例 2
50
操作を一度も行わないことで、\sum_{i=1}^N A_i を 50 にすることが可能です。
入力例 3
5 3 1 4 1 5
出力例 3
18
Score : 500 points
Problem Statement
You are given a sequence of non-negative integers A = (A_1, \ldots, A_N). You can do the operation below any number of times (possibly zero).
- Choose an integer x\in \{A_1,\ldots,A_N\}.
- Replace A_i with A_i\oplus x for every i (\oplus denotes the bitwise \mathrm{XOR} operation).
Find the maximum possible value of \sum_{i=1}^N A_i after your operations.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows:
- When A \oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.
Constraints
- 1\leq N \leq 3\times 10^{5}
- 0\leq A_i < 2^{30}
Input
Input is given from Standard Input from the following format:
N A_1 \ldots A_N
Output
Print the maximum possible value of \sum_{i=1}^N A_i after your operations.
Sample Input 1
5 1 2 3 4 5
Sample Output 1
19
Here is a sequence of operations that achieves \sum_{i=1}^N A_i = 19.
- Initially, the sequence A is (1,2,3,4,5).
- An operation with x = 1 changes it to (0,3,2,5,4).
- An operation with x = 5 changes it to (5,6,7,0,1), where \sum_{i=1}^N A_i = 5 + 6 + 7 + 0 + 1 = 19.
Sample Input 2
5 10 10 10 10 10
Sample Output 2
50
Doing zero operations achieves \sum_{i=1}^N A_i = 50.
Sample Input 3
5 3 1 4 1 5
Sample Output 3
18