A - XOR Cross Over 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 700 点

問題文

非負整数列が書かれている黒板があります。はじめ、黒板には長さ N の非負整数列 A=(A_1,A_2,\dots,A_N) のみが書かれています。

黒板に書かれている非負整数列の長さがすべて 1 になるまで以下の操作を行い続けます。

  • 黒板に書かれている非負整数列のうち、長さ 2 以上の非負整数列を 1 つ選び、黒板から消去する。選んだ非負整数列を B=(B_1,B_2,\dots,B_n) とする。続けて 1 \leq k < n を満たす整数 k を 1 つ選び、 X = B_1 \oplus B_2 \oplus \dots \oplus B_k,\ Y=B_{k+1} \oplus B_{k+2} \oplus \dots \oplus B_n とする。最後に黒板に 2 つの非負整数列 (B_1 \oplus Y, B_2 \oplus Y,\dots,B_k \oplus Y),\ (B_{k+1} \oplus X,\ B_{k+2} \oplus X,\dots,B_n \oplus X) を書き込む

ただしここで、 \oplus はビット単位 \mathrm{XOR} 演算を表します。

一連の操作を行った後、黒板に書かれている N 個の長さ 1 の非負整数列を (C_1),(C_2),\dots,(C_N) としたとき、 \sum_{i=1}^{N}C_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 である。
例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。

制約

  • 1 \leq N \leq 500
  • 0 \leq A_i < 2^{40}
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

4
1 3 4 5

出力例 1

6

はじめ、黒板には (1,3,4,5) のみが書かれています。ここから、以下の手順で操作を行います。

  1. (1,3,4,5) を黒板から消去し、 k=2 とする。 X=1 \oplus 3 = 2, Y= 4 \oplus 5 = 1 となり、黒板には新たに 2 つの非負整数列 (1 \oplus 1, 3 \oplus 1)=(0,2), (4 \oplus 2, 5 \oplus 2)=(6,7) が書き込まれる。
  2. (0,2) を黒板から消去し、 k=1 とする。黒板には新たに 2 つの非負整数列 (2),(2) が書き込まれる。
  3. (6,7) を黒板から消去し、 k=1 とする。黒板には新たに 2 つの非負整数列 (1),(1) が書き込まれる。

以上の手順により、黒板に書かれている非負整数列はいずれも長さ 1 の非負整数列 (2),(2),(1),(1) の 4 つになり、値の合計は 2+2+1+1=6 となります。

入力例 2

7
1 5 14 23 20 18 20

出力例 2

39

入力例 3

20
246260893965 450834729933 1091503137264 661761201979 238822689279 375606126051 183045127603 1004516515418 976478741401 957665143474 451659136716 828528157302 204109014940 184065081345 122138832666 130646707415 144391522538 87966805947 381909891703 343575641318

出力例 3

3597854777632

Score : 700 points

Problem Statement

(In this problem statement, all sequences consist of non-negative integers.)

There is a blackboard on which sequences are written. Initially, the blackboard only has one length-N sequence A=(A_1,A_2,\dots,A_N).

We repeat the following operation until all sequences on the blackboard are of length 1:

  • Among the sequences on the blackboard, choose one that has length at least 2, and remove it from the blackboard. Let the chosen sequence be B=(B_1,B_2,\dots,B_n). Then, choose an integer k satisfying 1 \leq k < n, and define X = B_1 \oplus B_2 \oplus \dots \oplus B_k and Y=B_{k+1} \oplus B_{k+2} \oplus \dots \oplus B_n. Finally, write two sequences (B_1 \oplus Y, B_2 \oplus Y,\dots,B_k \oplus Y) and (B_{k+1} \oplus X,\ B_{k+2} \oplus X,\dots,B_n \oplus X) on the blackboard.

Here, \oplus denotes the bitwise \mathrm{XOR} operation.

After this series of operations, let (C_1),(C_2),\dots,(C_N) be the N sequences of length 1 on the blackboard. Find the minimum possible value of \sum_{i=1}^{N} C_i.

Notes on the bitwise \mathrm{XOR} operation

For two non-negative integers A, B, the bitwise \mathrm{XOR} operation A \oplus B is defined as follows.

  • When A \oplus B is written in binary, for each 2^k place (k \geq 0), the bit is 1 if and only if exactly one of the bits in the 2^k place of A and B (in binary) is 1, and 0 otherwise.
For example, 3 \oplus 5 = 6 (in binary notation: 011 \oplus 101 = 110).
In general, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), and it can be proved that this value does not depend on the order of p_1, p_2, \dots, p_k.

Constraints

  • 1 \leq N \leq 500
  • 0 \leq A_i < 2^{40}
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4
1 3 4 5

Sample Output 1

6

Initially, the blackboard has (1,3,4,5) written on it. From here, we perform operations in the following steps.

  1. Remove (1,3,4,5) from the blackboard and set k=2. Then, X=1 \oplus 3=2 and Y=4 \oplus 5=1, and two new sequences (1 \oplus 1, 3 \oplus 1)=(0,2) and (4 \oplus 2, 5 \oplus 2)=(6,7) are written on the blackboard.
  2. Remove (0,2) from the blackboard and set k=1. Two new sequences (2),(2) are written on the blackboard.
  3. Remove (6,7) from the blackboard and set k=1. Two new sequences (1),(1) are written on the blackboard.

After these steps, the four sequences on the blackboard are (2),(2),(1),(1), each of length 1. Their sum is 2+2+1+1=6.

Sample Input 2

7
1 5 14 23 20 18 20

Sample Output 2

39

Sample Input 3

20
246260893965 450834729933 1091503137264 661761201979 238822689279 375606126051 183045127603 1004516515418 976478741401 957665143474 451659136716 828528157302 204109014940 184065081345 122138832666 130646707415 144391522538 87966805947 381909891703 343575641318

Sample Output 3

3597854777632