G - Stone XOR 解説 /

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

配点 : 400 点

問題文

袋 1, 袋 2, \ldots, 袋 N と番号づけられた N 個の袋があります。
袋 i (1\leq i\leq N) には A_i 個の石が入っています。

高橋君は次の操作を好きなだけ（0 回でも良い）繰り返すことができます。

2 つの袋 A, B を選び、袋 A に入っている石を すべて 袋 B に入れる。

操作を繰り返した後の状態における次の値としてあり得るものが何個あるか求めてください。

  • 袋 i に入っている石の個数を B_i として、B_1\oplus B_2\oplus\cdots\oplus B_N の値。
    ただし、\oplus は排他的論理和を表す。
排他的論理和とは 非負整数 a,b の排他的論理和 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 個の非負整数 x_1, x_2, \ldots, x_k の排他的論理和 x_1\oplus x_2\oplus\cdots\oplus x_k は (\cdots((x_1 \oplus x_2) \oplus x_3) \oplus \cdots \oplus x_k) と定義され、 これは x_1, x_2, \ldots, x_k の順番によらないことが証明できます。

なお、問題の制約下において、操作を繰り返した後の状態における上記の値としてあり得るものが有限個しかないことが証明できます。

制約

  • 2\leq N \leq 12
  • 1\leq A_i \leq 10^{17}
  • 入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

出力

高橋君が操作を繰り返した後の状態における、問題文中で定義された値としてあり得るものの個数を出力せよ。

入力例 1

3
2 5 7

出力例 1

3

例えば、高橋君が袋 A, B として袋 1, 3 を選び、操作を行ったとすると、袋 1,2,3 に入っている石はそれぞれ 0,5,9 となります。
ここで高橋君が操作を終了したとき、この状態における、袋に入っている石の個数の排他的論理和は 0\oplus 5\oplus 9=12 となります。

他に、高橋君が操作を繰り返した後の状態における、袋に入っている石の個数の排他的論理和としてあり得るものは 0,14 があります。
よって、あり得る値は 0,12,14 の 3 個であるため、3 を出力します。

入力例 2

2
100000000000000000 100000000000000000

出力例 2

2

入力例 3

6
71 74 45 34 31 60

出力例 3

84

Score : 400 points

Problem Statement

There are N bags, labeled bag 1, bag 2, \ldots, bag N.
Bag i (1 \leq i \leq N) contains A_i stones.

Takahashi can perform the following operation any number of times, possibly zero:

Choose two bags A and B, and move all stones from bag A into bag B.

Find the number of different possible values for the following after repeating the operation.

  • B_1 \oplus B_2 \oplus \cdots \oplus B_N, where B_i is the final number of stones in bag i.
    Here, \oplus denotes bitwise XOR.
About bitwise XOR For non-negative integers a and b, the bitwise XOR a \oplus b is defined as follows:
In the binary representation of a \oplus b, the digit in the 2^k place (k \ge 0) is 1 if and only if exactly one of the digits in the 2^k place of a and b is 1; otherwise, it is 0.
For example, 3 \oplus 5 = 6 (in binary, 011 \oplus 101 = 110).
In general, for k non-negative integers x_1, x_2, \ldots, x_k, their bitwise XOR x_1 \oplus x_2 \oplus \cdots \oplus x_k is defined as (\cdots((x_1 \oplus x_2) \oplus x_3) \oplus \cdots) \oplus x_k, which does not depend on the order of x_1, x_2, \ldots, x_k.

It can be proved that under the constraints of this problem, the number of possible values is finite.

Constraints

  • 2 \leq N \leq 12
  • 1 \leq A_i \leq 10^{17}
  • All input values are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print the number of different possible values for B_1 \oplus B_2 \oplus \cdots \oplus B_N after repeating the operation.

Sample Input 1

3
2 5 7

Sample Output 1

3

For example, if Takahashi chooses bags 1 and 3 for the operation, then the numbers of stones in bags 1, 2, 3 become 0, 5, 9.
If he stops at this point, the XOR is 0 \oplus 5 \oplus 9 = 12.

The other possible XOR values after repeating the operation are 0 and 14.
Therefore, the possible values are 0, 12, 14; there are three values, so the output is 3.

Sample Input 2

2
100000000000000000 100000000000000000

Sample Output 2

2

Sample Input 3

6
71 74 45 34 31 60

Sample Output 3

84