CF1534E Lost Array

这是一个交互题。 注意：一个数组 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）的异或和被定义为 $a_1 \oplus a_2 \oplus \ldots \oplus a_n$，其中 $\oplus$ 表示[按位异或操作](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。 Little Dormi 收到了一份长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$ 作为圣诞礼物。然而，在寒假玩耍时，他不小心把它掉进了他的异或机，结果数组丢失了。 异或机当前配置的查询大小为 $k$（你无法更改），它允许你进行如下类型的查询：你可以给出 $k$ 个互不相同的下标 $x_1, x_2, \ldots, x_k$，机器会输出 $a_{x_1} \oplus a_{x_2} \oplus \ldots \oplus a_{x_k}$。 作为 Little Dormi 的哥哥，你想帮他通过查询异或机，恢复整个数组 $a_1, a_2, \ldots, a_n$ 的异或和。 Little Dormi 没有耐心，所以你必须用最少的查询次数找到异或和。形式化地，设 $d$ 为在查询大小为 $k$ 的情况下，恢复任意长度为 $n$ 的数组异或和所需的最小查询次数。只要你在不超过 $d$ 次查询内找出正确的异或和，你的程序就会被接受。 最后，你还注意到，对于某些 $k$ 和 $n$ 的配置，可能无法恢复 Little Dormi 丢失的数组的异或和。如果是这种情况，你也需要报告。 数组 $a_1, a_2, \ldots, a_n$ 在你开始查询前已经固定，并且在查询过程中不会改变。

输入仅一行，包含整数 $n$ 和 $k$（$1 \le n \le 500$，$1 \le k \le n$），分别表示丢失数组的长度和异或机的查询大小。 原始数组的元素满足 $1 \le a_i \le 10^9$。 可以保证，如果在给定约束下可以恢复异或和，则最多只需 $500$ 次查询，即 $d \le 500$。 在读入 $n$ 和 $k$ 后，开始交互。

如果无法恢复数组的异或和，读入 $n$ 和 $k$ 后应立即输出 $-1$，并且不要开始交互。 否则，当你的程序找到了丢失数组 $a_1, a_2, \ldots, a_n$ 的异或和后，应按以下格式报告答案：“! x”，其中 $x$ 是数组 $a_1, a_2, \ldots, a_n$ 的异或和，并在输出后立即刷新输出流并正常终止程序。 注意，输出答案不计入查询次数。 交互说明 每次查询的格式为“? b”，其中 $b$ 是一个恰好包含 $k$ 个互不相同的 $1$ 到 $n$ 的整数，表示你想查询的数组下标。 你将收到一个整数 $x$，表示所查询元素的异或和。可以保证 $0 \le x \le 2 \cdot 10^9$。 每次输出查询后，不要忘记输出换行并刷新输出流，否则会导致 Idleness limit exceeded。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请查阅相关文档 如果你进行了一次非法查询，或查询次数超过 $500$（这是硬性上限），交互将立即终止并返回 Wrong Answer。注意，如果你超过了 $d$ 次查询，交互仍会继续，除非你也超过了 $500$ 次查询的硬性上限，但你仍会收到 Wrong Answer。 Hack 格式 要 hack 一个解答，使用如下格式： 第一行包含整数 $n$ 和 $k$（$1 \le n \le 500$，$1 \le k \le n$）。 第二行包含数组 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）。

在第一个交互样例中，数组 $a_1, a_2, \ldots, a_n$ 为 $2, 1, 7, 5, 6$，其异或和为 $7$。 第一次查询索引 $1,2,3$，返回 $a_1 \oplus a_2 \oplus a_3 = 2 \oplus 1 \oplus 7 = 4$。 第二次查询索引 $2,3,5$，返回 $a_2 \oplus a_3 \oplus a_5 = 1 \oplus 7 \oplus 6 = 0$。 第三次查询索引 $4,1,5$，返回 $a_4 \oplus a_1 \oplus a_5 = 5 \oplus 2 \oplus 6 = 1$。注意索引顺序可以任意。 此外，虽然样例中进行了三次查询，但这只是为了演示交互格式，并不一定代表最优策略。 在第二个交互样例中，无论如何都无法恢复 Little Dormi 的数组异或和，因此程序应立即输出 $-1$ 并退出。 由 ChatGPT 4.1 翻译