分数: 800 点
问题陈述
在数轴上,有 2^N-1 球位于坐标处 x=1,2,3,...,2^N-1,球位于 x=i 的权重为 w_i。在这里, w_1, w_2,...,w_{2^N-1} 是以下整数的排列 1 通过 2^N-1。您将选择一个非负整数 Z 最多 2^N-1 并附加一个重量 Z 在每个坐标处 x=\pm 100^{100^{100}}。 然后,球将同时开始移动,如下所示。
- 每次,让 R 为总计 \mathrm{XOR} 球的重量和严格位于球坐标右侧的附加重量,以及 L 为总计 \mathrm{XOR} 球的重量和严格位于左侧的附加重量。如果 R>L,球以速度向右移动 1 每秒;如果 L>R,球以速度向左移动 1 每秒;如果 L=R,球静止不动。
- 如果同一坐标处存在多个球(例如,当左右两个球到达该坐标时),这些球会合并为一个,其重量为总重量 \mathrm{XOR} 他们以前的体重。
有多少个值 Z 所有的球都会停在 100^{100} 秒?
什么是 \mathrm{XOR}?
按位 \mathrm{XOR} 非负整数 A 和 B, A \oplus B定义如下。
- 当 A \oplus B 以二进制形式写入, k- 第最低位 (k \geq 0) 是 1 如果恰好是其中之一 k- 第最低位 A 和 B is 1,和 0 否则。
一般来说,按位 \mathrm{XOR} of k 非负整数 p_1, p_2, p_3, \dots, p_k 定义为 (\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
- w_i\neq w_j if i\neq j.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
w_1 w_2 \ldots w_{2^N-1}
输出
将答案打印为整数。
示例输入 1
2 1 2 3
示例输出 1
1
让我们称一个重量为 i 简单地说 i.
If Z=0,例如, 1 和 2 首先向右移动,然后 3 向左移动。 然后,那一刻 2 和 3 碰撞并组合成一个球,它开始向左移动。 随后,所有球从 1 to 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