背景

试题来自 清华大学学生算法协会。

题目描述

给定一个长度为 $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$ 的内容。

输出格式

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

1
3 5

14

2
2 6 8 8

0

提示

以下是样例 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 完成