201352: [AtCoder]ARC135 C - XOR to All

Memory Limit：1024 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

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.
For example, we have $3 \oplus 5 = 6$ (in base two: $011 \oplus 101 = 110$).

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

Input

题意翻译

## 题目描述 给定 $n$ 个非负整数 $a_1,a_2,\dots,a_n$，你可以执行以下操作任意（可以为零）次： - 选择一个数 $x\in \{a_1,a_2,\dots,a_n\}$。 - 对于所有 $a\leq i\leq n$，将 $a_i$ 修改为 $a_i\oplus x$，其中 $\oplus$ 表示按位异或操作。 请你最大化操作后 $\sum_{i=1}^na_i$ 的值。 ## 输入格式 第一行一个整数 $n$。 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。 ## 输出格式 一行一个整数，表示操作后 $\sum_{i=1}^na_i$ 的最大值。 ## 样例 #1 ### 样例输入 #1 ``` 5 1 2 3 4 5 ``` ### 样例输出 #1 ``` 19 ``` ## 样例 #2 ### 样例输入 #2 ``` 5 10 10 10 10 10 ``` ### 样例输出 #2 ``` 50 ``` ## 样例 #3 ### 样例输入 #3 ``` 5 3 1 4 1 5 ``` ### 样例输出 #3 ``` 18 ``` ## 提示 ### 数据范围 - $1\leq n \leq 3\times 10^5$ - $0\leq a_i<2^{30}$

Source/Category

加入题单

上一题 下一题 算法标签：