/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
長さ N の数列 A が与えられます。
この数列を、1 つ以上の空でない連続した区間に分けます。
その後、分けた各区間で、区間内の数のビット単位 \mathrm{OR} を計算します。
こうして得られた全ての値のビット単位 \mathrm{XOR} として考えられる最小値を求めてください。
ビット単位 \mathrm{OR} 演算とは
整数 A, B のビット単位 \mathrm{OR}、A\ \mathrm{OR}\ B は以下のように定義されます。
- A\ \mathrm{OR}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち少なくとも片方が 1 であれば 1、そうでなければ 0 である。
一般に k 個の整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{OR} は (\dots ((p_1\ \mathrm{OR}\ p_2)\ \mathrm{OR}\ p_3)\ \mathrm{OR}\ \dots\ \mathrm{OR}\ p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。
ビット単位 \mathrm{XOR} 演算とは
整数 A, B のビット単位 \mathrm{XOR} 、A\ \mathrm{XOR}\ B は、以下のように定義されます。
- A\ \mathrm{XOR}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個以上の整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。
制約
- 1 \le N \le 20
- 0 \le A_i \lt 2^{30}
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 A_3 \dots A_N
出力
答えを出力せよ。
入力例 1
3 1 5 7
出力例 1
2
[1, 5, 7] を [1, 5] と [7] の 2 つの区間に分けると、それぞれの区間内の数のビット単位 \mathrm{OR} は 5, 7 となり、その \mathrm{XOR} は 2 です。
これより小さくすることはできないので、2 を出力します。
入力例 2
3 10 10 10
出力例 2
0
[10] と [10, 10] に分けるとよいです。
入力例 3
4 1 3 3 1
出力例 3
0
[1, 3] と [3, 1] に分けるとよいです。
Score : 300 points
Problem Statement
Given is a number sequence A of length N.
Let us divide this sequence into one or more non-empty contiguous intervals.
Then, for each of these intervals, let us compute the bitwise \mathrm{OR} of the numbers in it.
Find the minimum possible value of the bitwise \mathrm{XOR} of the values obtained in this way.
What is bitwise \mathrm{OR}?
The bitwise \mathrm{OR} of integers A and B, A\ \mathrm{OR}\ B, is defined as follows:
- When A\ \mathrm{OR}\ B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if at least one of A and B is 1, and 0 otherwise.
Generally, the bitwise \mathrm{OR} of k integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1\ \mathrm{OR}\ p_2)\ \mathrm{OR}\ p_3)\ \mathrm{OR}\ \dots\ \mathrm{OR}\ p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots p_k.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of integers A and B, A\ \mathrm{XOR}\ B, is defined as follows:
- When A\ \mathrm{XOR}\ 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.
Generally, the bitwise \mathrm{XOR} of k integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k). We can prove that this value does not depend on the order of p_1, p_2, p_3, \dots p_k.
Constraints
- 1 \le N \le 20
- 0 \le A_i \lt 2^{30}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 A_3 \dots A_N
Output
Print the answer.
Sample Input 1
3 1 5 7
Sample Output 1
2
If we divide [1, 5, 7] into [1, 5] and [7], their bitwise \mathrm{OR}s are 5 and 7, whose \mathrm{XOR} is 2.
It is impossible to get a smaller result, so we print 2.
Sample Input 2
3 10 10 10
Sample Output 2
0
We should divide this sequence into [10] and [10, 10].
Sample Input 3
4 1 3 3 1
Sample Output 3
0
We should divide this sequence into [1, 3] and [3, 1].