AT_arc152_e.[ARC152E] Xor Annihilation

在数轴上的 $x=1,2,3,\ldots,2^N-1$ 位置上，依次排列着 $2^N-1$ 个小球，第 $x=i$ 位置上的小球的重量为 $w_i$。其中，$w_1,w_2,\ldots,w_{2^N-1}$ 是 $1$ 到 $2^N-1$ 的一个排列。此外，你可以选择一个不超过 $2^N-1$ 的非负整数 $Z$，并将重量为 $Z$ 的小球分别固定在坐标 $x=+100^{100^{100}}$ 和 $x=-100^{100^{100}}$ 上。之后，所有小球会同时按照如下规则开始运动：

• 在任意时刻，对于每个小球，记其所在坐标右侧所有小球的重量的 $\mathrm{XOR}$ 为 $R$，左侧所有小球的重量的 $\mathrm{XOR}$ 为 $L$。若 $R>L$，则该小球以每秒 $1$ 的速度向右移动；若 $L>R$，则向左移动；若 $L=R$，则静止不动。
• 若有多个小球同时到达同一坐标（包括从左右方向相遇），它们会合并成一个小球，合并后小球的重量为合并前所有小球重量的 $\mathrm{XOR}$。

请问，有多少个 $Z$ 能够使得所有小球在 $100^{100}$ 秒内全部静止？

$\mathrm{XOR}$ 是指非负整数 $A,B$ 的按位异或，记作 $A\oplus B$，定义如下：

• $A\oplus B$ 的二进制表示中，每一位 $2^k$（$k\geq 0$）上的数等于 $A,B$ 的二进制表示在该位上恰有一个为 $1$ 时为 $1$，否则为 $0$。

例如，$3\oplus 5=6$（二进制为：$011\oplus 101=110$）。
一般地，$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)$，且可以证明其与顺序无关。

输入通过标准输入给出，格式如下：

$N$ $w_1$ $w_2$ $\ldots$ $w_{2^N-1}$

输出一个整数，表示满足条件的 $Z$ 的个数。

数据范围

• $2\leq N\leq 18$
• $1\leq w_i\leq 2^N-1$
• 当 $i\neq j$ 时 $w_i\neq w_j$
• 输入的所有值均为整数

样例解释 1

我们将重量为 $i$ 的小球简称为 $i$。例如，当 $Z=0$ 时，初始时 $1$ 和 $2$ 向右移动，$3$ 向左移动。随后 $2$ 和 $3$ 相遇并合并，合并后的小球开始向左移动。最终，当 $1$ 到 $3$ 的所有小球合并后，合并后的小球静止。因此，$Z=0$ 满足条件。而当 $Z=3$ 时，$1$ 和 $2$ 向左移动，$3$ 向右移动，所有小球会朝着固定的重量移动很长时间，因此 $Z=3$ 不满足条件。实际上，只有 $Z=0$ 满足条件，所以答案为 $1$。

由 ChatGPT 4.1 翻译