# 【题目】XOR to All

AtCoder Regular Contest 135

C - XOR to All

Time Limit: 2 sec / Memory Limit: 1024 MB

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.

### 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.

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$.

5
10 10 10 10 10

### Sample Output 2

50

Doing zero operations achieves $\sum_{i=1}^N A_i = 50$.

5
3 1 4 1 5

18

### 代码

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<int> A(N);
vector<int> bit(30);
for (int i = 0; i < N; i++)
{
cin >> A[i];
int t = A[i];
for (int i = 0; t; i++, t >>= 1)
{
bit[i] += t & 1;
}
}
long long sum = accumulate(A.begin(), A.end(), 0LL);
for (int i = 0; i < N; i++)
{
long long cur_sum = 0, d = 1;
int t = A[i], bit_sum;
for (int j = 0; j < 30; j++)
{
if (t & 1)
{
bit_sum = N - bit[j];
}
else
{
bit_sum = bit[j];
}
t >>= 1;
cur_sum += d * bit_sum;
d <<= 1;
}
sum = max(sum, cur_sum);
}
cout << sum << endl;
return 0;
}