/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
数直線上の x=1,2,3,...,2^N-1 の位置に 2^N-1 個のボールが並んでおり、x=i にあるボールは w_i の重みを持っています。ただし、w_1, w_2,...,w_{2^N-1} は 1 から 2^N-1 までの整数を並び替えた数列です。 さらに、あなたは 2^N-1 以下の負でない整数 Z を 1 つ選び、座標 x=\pm 100^{100^{100}} にそれぞれ Z の重みを固定します。 その後、各ボールは次の規則にしたがって、一斉に運動を始めます。
- 各時点で、ボールの存在している座標より真に右側にある座標・ボールの重みの総 \mathrm{XOR} を R、真に左側にある座標・ボールの重みの総 \mathrm{XOR} を L とすると、このボールは R>L であれば右側に、L>R であれば左側に毎秒 1 の速さで動き、L=R であれば静止する。
- 左右から来たボールが同じ座標に到達したときなど、同じ座標に同時に複数のボールが存在した場合、これらのボールは合体し、その重みは合体前の重みの総 \mathrm{XOR} となる。
このとき、100^{100} 秒以内に全てのボールが静止するような Z はいくつあるでしょうか。
\mathrm{XOR} とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus 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 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。
制約
- 2\leq N\leq 18
- 1\leq w_i\leq 2^N-1
- i\neq j のとき w_i\neq w_j
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N
w_1 w_2 \ldots w_{2^N-1}
出力
答えを整数で出力せよ。
入力例 1
2 1 2 3
出力例 1
1
i の重みを持つボールを単に i と呼びます。
例えば Z=0 とした場合、はじめ 1 と 2 は右向きに、3 は左向きに動きます。 すると 2 と 3 がぶつかって合体し、この瞬間から左向きに動き始めます。 そののち、1 から 3 まで全てのボールが合体した瞬間に合体後のボールは静止します。 したがって、Z=0 は条件を満たします。
また、Z=3 とした場合、1 と 2 は左向き、3 は右向きに、固定した重みに向かって 100^{100^{100}} 秒程度動き続けることになります。 したがって、Z=3 は条件を満たしません。
実は Z=0 のみが条件を満たすため、1 と答えてください。
入力例 2
3 7 1 2 3 4 5 6
出力例 2
2
Score : 800 points
Problem Statement
On a number line, there are 2^N-1 balls at the coordinates x=1,2,3,...,2^N-1, and the ball at x=i has a weight of w_i. Here, w_1, w_2,...,w_{2^N-1} is a permutation of the integers from 1 through 2^N-1. You will choose a non-negative integer Z at most 2^N-1 and attach a weight of Z at each of the coordinates x=\pm 100^{100^{100}}. Then, the balls will simultaneously start moving as follows.
- At each time, let R be the total \mathrm{XOR} of the weights of the balls and attached weights that are strictly to the right of the coordinate of a ball, and L be the total \mathrm{XOR} of the weights of the balls and attached weights that are strictly to the left. If R>L, the ball moves to the right at a speed of 1 per second; if L>R, the ball moves to the left at a speed of 1 per second; if L=R, the ball stands still.
- If multiple balls exist at the same coordinate (when, for instance, two balls coming from the left and right reach there), the balls combine into one whose weight is the total \mathrm{XOR} of their former weights.
For how many values of Z will all balls come to rest within 100^{100} seconds?
What is \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 binary, the k-th lowest bit (k \geq 0) is 1 if exactly one of the k-th lowest bits of A and B is 1, and 0 otherwise.
Generally, 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), which can be proved to be independent of the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 2\leq N\leq 18
- 1\leq w_i\leq 2^N-1
- w_i\neq w_j if i\neq j.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N
w_1 w_2 \ldots w_{2^N-1}
Output
Print the answer as an integer.
Sample Input 1
2 1 2 3
Sample Output 1
1
Let us call a ball with a weight of i simply i.
If Z=0, for instance, 1 and 2 first move to the right, and 3 moves to the left. Then, the moment 2 and 3 collide and combine into one ball, it starts moving to the left. Afterward, the moment all balls from 1 to 3 combine into one ball, it stands still. Thus, Z=0 satisfies the condition.
On the other hand, if Z=3, then 1 and 2 keep moving to the left, and 3 keeps moving to the right, toward the attached weights for approximately 100^{100^{100}} seconds. Thus, Z=3 does not satisfy the condition.
It turns out that Z=0 is the only value that satisfies the condition, so you should print 1.
Sample Input 2
3 7 1 2 3 4 5 6
Sample Output 2
2