P17124 [ICPC 2025 Shanghai R] Not a subset sum

试题来自 [清华大学学生算法协会](https://gitlink.org.cn/thusaa/ICPC2025shanghai)。

给定一个长度为 $2^n$ 的数组 $a_0, a_1, \cdots, a_{2^n - 1}$。对于一个由字符 $0, 1, ?$ 组成的长度为 $n$ 的字符串 $q$（下标从 $1$ 开始），定义“广义子集和” $S(q)$ 为所有满足以下条件的下标 $j$ 对应的 $a_j$ 之和： - 对于每个 $1 \le k \le n$，如果 $q_k = 0$，则 $j$ 的第 $k$ 位为 $0$。 - 对于每个 $1 \le k \le n$，如果 $q_k = 1$，则 $j$ 的第 $k$ 位为 $1$。 - 如果 $q_k = ?$，则对 $j$ 的第 $k$ 位没有限制。 例如，当 $n = 3$ 且 $q = 0?1$ 时，广义子集和为 $S(q) = a_4 + a_6$（即二进制 $100$ 和 $110$）。注意，第一位是最低位。 你的任务是计算所有长度为 $n$、由字符 $0, 1, ?$ 构成的字符串所对应的广义子集和。因为输出总量可能很大，你只需输出所有这些和的**按位异或**结果。

输入的第一行包含一个整数 $n$ ($1 \le n \le 16$)。 输入的第二行包含 $2^n$ 个整数 $a_0, a_1, \cdots, a_{2^n - 1}$ ($0 \le a_i \le 9$)，即数组 $a$ 的内容。

输出一个整数，表示所有广义子集和的按位异或。

以下是**样例 2** 中的查询字符串 $q$ 及其对应的广义子集和 $S(q)$： $q = 00$, $S(q) = a_0 = 2$ $q = 10$, $S(q) = a_1 = 6$ $q = ?0$, $S(q) = a_0 + a_1 = 2 + 6 = 8$ $q = 01$, $S(q) = a_2 = 8$ $q = 11$, $S(q) = a_3 = 8$ $q = ?1$, $S(q) = a_2 + a_3 = 16$ $q = 0?$, $S(q) = a_0 + a_2 = 10$ $q = 1?$, $S(q) = a_1 + a_3 = 14$ $q = ??$, $S(q) = a_0 + a_1 + a_2 + a_3 = 24$ 现在容易验证输出为 $0$。 翻译由 DeepSeek V4 Pro 完成