异或多重集 - 문제

给你一个整数 $n$ 和 $n - 1$ 个非负整数 $a_1, a_2, \dots, a_{n-1}$。

请寻找一个由 $\{1, 2, \dots, n - 1\}$ 中的整数组成的多重集 $S$，满足：

$\sum_{x \in S} x \equiv 0 \pmod n$
$\bigoplus_{x \in S} a_x$ 最大，其中 $\bigoplus$ 表示按位异或（XOR）运算。按位异或运算符作用于两个数的二进制表示，并对每对相应的位执行逻辑异或操作；例如 5（二进制表示为 0101）XOR 3（二进制表示为 0011）得到 6（二进制表示为 0110）。在 C++、Java 和 Python 中，该运算符为 ^。

如果存在多个这样的多重集，你可以返回其中任意一个。

你需要实现以下函数：

(int64, int32[]) find_multiset(int32 n, int64[] a)

n：模数
a：长度为 $n - 1$ 的数组，其中 a[i] 对应 $a_{i+1}$
该函数应返回一个二元组（pair）：
- 第一个元素：一个整数，表示在所有合法的多重集 $S$ 中，$\bigoplus_{x \in S} a_x$ 的最大值。
- 第二个元素：一个 vector，表示任意一个达到该最大值的合法多重集 $S$。vector 中的元素应为 $1$ 到 $n - 1$ 之间的整数，且 $S$ 的大小最多为 $2n$。

在每个子任务中，如果你的程序确定了所有合法多重集 $S$ 中 $\bigoplus_{x \in S} a_x$ 的最优值，你就可以获得部分分数。更具体地说：

如果在该子任务的所有测试用例中，find_multiset 返回的二元组的第一个元素与官方评测程序返回的第一个元素完全相同，且第二个元素是一个实现了该最优值的合法多重集（即满足上述条件），你将获得该子任务的满分。
如果在该子任务的所有测试用例中，find_multiset 返回的二元组的第一个元素与官方评测程序返回的第一个元素完全相同（无论第二个元素如何），你将获得该子任务 60% 的分数。
否则，你将获得该子任务 0% 的分数。

调用 find_multiset(3, {5, 10}) 应返回 {15, {1, 2}}：

我们有 $n = 3$ 且 $a = [5, 10]$（对应 $a_1 = 5, a_2 = 10$）。
我们需要寻找一个多重集 $S \subseteq \{1, 2\}$ 使得 $\sum_{x \in S} x \equiv 0 \pmod 3$。
合法的多重集包括：$\emptyset$（和为 0），$\{1, 2\}$（和为 $3 \equiv 0$），$\{1, 1, 1\}$（和为 $3 \equiv 0$），$\{2, 2, 2\}$（和为 $6 \equiv 0$）等。
对于 $S = \{1, 2\}$：异或值为 $a_1 \oplus a_2 = 5 \oplus 10 = 15$。
对于 $S = \{1, 1, 1\}$：异或值为 $a_1 \oplus a_1 \oplus a_1 = 5 \oplus 5 \oplus 5 = 5$。
最大异或值为 15，由 $S = \{1, 2\}$ 达到。

调用 find_multiset(4, {8, 12, 6}) 应返回 {14, {1, 3}}：

样例评测程序按以下格式读取输入：

样例评测程序调用 find_multiset(n, a) 并按以下格式输出返回的多重集：

本题提供的样例评测程序仅用于在本地测试你的解决方案。比赛中实际使用的评测程序可能有所不同。

QOJ.ac