201524: [AtCoder]ARC152 E - Xor Annihilation

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

Description

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.
For instance, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).
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

Input

题意翻译

一条直线上有 $2^N-1$ 个初始坐标分别为 $1 \sim 2^N-1$ 的动点。其中坐标为 $i$ 的点有一个权值 $w_i$。 现在你要在 $+100^{100^{100}}$ 和 $-100^{100^{100}}$ 坐标处各加一个不超过 $2^N-1$ 非负权值 $Z$，然后 $2^N-1$ 个点会按照下列规则同时从初始坐标开始移动： - 每个单位时间内，记严格小于一个点的坐标的权值异或和为 $L$，严格大于这个点的权值异或和为 $R$。当 $L < R$ 时，这个点会以 $1$ 个单位长度每个单位时间的速度向右移动；$L > R$ 时则会以同样速度向左移动；$L = R$ 时，这个点会静止不动。 - 当两个点在同一时间到达同一坐标时，这两个点会合并成一个点，新点的权值为两个点权值的异或和。 请求出可以使所有点在 $100^{100}$ 个单位时间内静止下来的 $Z$ 的个数。 （注：$+100^{100^{100}}$ 和 $-100^{100^{100}}$ 处只是增加了 $Z$ 的权值，初始时并没有动点。） 保证 $2 \le N \le 18$，$1 \le w_i \le 2^N-1$ 且 $i \not = j$ 时 $w_i \not = w_j$，输入的所有数均为整数。 [何为异或和](https://oi-wiki.org/math/bit/#%E4%B8%8E%E6%88%96%E5%BC%82%E6%88%96)

Source/Category

加入题单

上一题 下一题 算法标签：