题目描述

给定一个整数 $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 翻译