P14037 [PAIO 2025] XOR multiset

**DO NOT** include `xor.h`. Submit using C++ >=17.

给定一个整数 $n$ 和 $n-1$ 个非负整数 $a_1, a_2, \dots, a_{n-1}$。 请你找到一个多重集 $S$，其元素均选自 $\{1, 2, \dots, n-1\}$，满足以下要求： * $\sum_{x \in S} x \equiv 0 \pmod n$； * $\bigoplus_{x \in S} a_x$ 的值最大，其中 $\bigoplus$ 表示按位异或运算。按位异或运算会作用于两个数的二进制，每一位分别异或。例如 $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}$； * 函数需返回一个二元组： * 第一个元素为 $\bigoplus_{x \in S} a_x$ 在所有合法 $S$ 中的最大值； * 第二个元素为满足要求的任意一个最优多重集 $S$。$S$ 的元素范围为 $1$ 到 $n-1$，大小不超过 $2n$。

无特殊输入格式说明。

无特殊输出格式说明。

## 样例 `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$。 * 合法多重集如：$\varnothing$（和为 $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}}` * 此时 $n=4$，$a=\{8,12,6\}$(即 $a_1=8, a_2=12, a_3=6$)。 * 目标是找到 $S \subseteq \{1, 2, 3\}$，要求 $\sum_{x \in S} x \equiv 0 \pmod 4$。 * $S = \{1, 3\}$ 时，结果为 $a_1 \oplus a_3 = 8 \oplus 6 = 14$。 * $S = \{2, 2\}$ 时，结果为 $a_2 \oplus a_2 = 12 \oplus 12 = 0$。 * 最大异或值为 $14$，由 $S = \{1, 3\}$ 达成。 ## 样例评测器 样例评测器输入格式如下： * 第一行：一个整数 $n$。 * 第二行：$n-1$ 个整数 $a_1,a_2,\dots,a_{n-1}$。 评测器调用 `find_multiset(n, a)` 并输出如下格式： * 第一行：函数返回对的第一个元素； * 第二行：多重集的大小； * 第三行：多重集中的元素（如有），用空格分隔。 **注意**：样例评测器仅供本地测试。正式考试中的评测方式可能有所不同。 # 数据范围 * $1 \le n \le 10^5$ * $0 \le a_i < 2^{62}$，$i = 1,2,\dots,n-1$ # 评分标准 * 子任务1（20分）：$n \le 10$ * 子任务2（40分）：$n$ 为奇数 * 子任务3（40分）：无额外约束 每个子任务，若你输出的最大异或值与标准答案一致且多重集 $S$ 合法且能达到最大值，则可获得该子任务的全部分数。若所有测试点最大异或值正确而 $S$ 任意但合法，则该子任务 60% 得分。其余情况得分为 0%。 由 ChatGPT 5 翻译