P11629 [WC2025] Nim 游戏

WC 2025 d1t2。

小 w 被迫卷入了一场决定一切的 Nim 游戏！ 有 $n$ 堆石子摆在小 w 面前，从 $1$ 到 $n$ 编号，其中编号为 $i$ 的石子堆中有 $a_i$ 个石子。在 Nim 游戏中，小 w 和一位绝顶聪明的对手轮流操作，小 w 后手。每次操作中，操作方可以选择一堆石子，将这一堆石子中任意多的石子扔掉，但不能不扔。如果某个人操作时，所有 $n$ 堆石子中都没有石子了，那么他就无法操作，从而失败。 熟练掌握 OI 知识的小 w 知道 Nim 游戏的最优策略，还知道两个玩家都以最优策略操作时，后手获胜当且仅当所有 $a_i$ 的按位异或和为 $0$。然而初始局面不一定满足这个条件，于是小 w 决定用些盘外招让所有 $a_i$ 的异或和为 $0$，然后赢下这盘游戏。为此小 w 准备了很多石子，他可以在游戏开始前在每个石子堆上添加任意多（也可以不添加）石子。然而小 w 不能从石子堆里取走石子，也不能创建新的石子堆。 小 w 请你提供添加石子的方案。为了保持隐蔽，小 w 希望添加尽可能少的石子，所以他首先想要知道最少需要添加多少石子。除此之外他还希望准备 $m$ 套不同的添加石子数最少的方案，以备不时之需。我们认为两种方案不同，当且仅当存在某堆石子，在这两种方案中该堆石子所添加的石子数量不同。如果这样的方案没有 $m$ 种，则你需要全部告诉他；如果这样的方案大于 $m$ 种，则你任意给出 $m$ 种即可。

**本题有多组测试数据**。 输入的第一行包含两个整数 $c,T$，分别表示测试点编号与测试数据组数。对于样例有 $c = 0$。 接下来依次输入每组测试数据，对于每组测试数据： 第一行包含两个整数 $n$ 和 $m$，分别表示石子堆的数量以及小 w 需要的方案数量。 第二行包含 $n$ 个非负整数 $a_1, a_2, \cdots , a_n$，描述每堆石子的石子数量。

对于每组测试数据： - 输出的第一行包含一个整数 $k$，表示小 w 最少需要添加多少石子。 - 输出的第二行包含一个整数 $m'$，表示你提供给小 w 的方案数量。如果添加石子最少的方案数不少于 $m$，你需要保证 $m' = m$，否则你需要保证 $m'$ 恰好是添加石子最少的方案数。 - 接下来依次输出 $m'$ 个不同的方案，对于每个方案输出三行，其中： * 第一行包含一个整数 $n'$，表示该方案中添加了石子的石子堆数量。 * 第二行包含 $n'$ 个整数 $x_1, x_2,\cdots , x_n'$，描述该方案中添加了石子的石子堆编号。你需要保证 $1 \le x_1 \lt x_2 \lt \cdots \lt x_{n'} \le n$。当 $n' = 0$ 时，这一行需要为空行。 * 第三行包含 $n'$ 个整数 $w_1,w_2,\cdots ,w_{n'}$，其中 $w_j(1 \le j \le n')$ 表示该方案中在编号为 $x_j$ 的石子堆中添加的石子数量。你需要保证对于任意的 $1 \le j \le n'$，有 $w_j \ge 1$ 且 $\sum_{j=1}^{n'} w_j=k$。当 $n' = 0$ 时，这一行需要为空行。 你需要保证在单个测试点内输出的整数数量不超过 $10^7$，可以保证总是存在这样的输出满足题目条件。

### 样例解释 #### 样例 $1$ 解释 对于第一组数据，小 w 共有两种使添加石子总数最小的方案： - 给编号为 $1$ 的石子堆添加 $2$ 个石子，给编号为 $3$ 的石子堆添加 $1$ 个石子。此时三堆石子数分别是 $6, 2, 4$，后手必胜。 - 给编号为 $3$ 的石子堆添加 $3$ 个石子。此时三堆石子数分别是 $4, 2, 6$，后手必胜。 由于小 w 只需要一种方案，输出任意一种方案均可，样例输出为第一种。 对于第二组数据，小 w 只有一种使添加石子总数最小的方案： - 给编号为 $1$ 的石子堆添加 $2$ 个石子。此时两堆石子的石子分别是 $3, 3$，此时后手必胜。 尽管小 w 需要两种方案，但由于总方案只有一种，故输出唯一的一种方案即可。 ### 数据范围 设 $\sum n$ 和 $\sum m$ 分别表示单个测试点的所有测试数据中 $n$ 和 $m$ 的和。 对于所有测试数据，保证： - $1 \le T \le 2 \times 10^4$； - $2 \le n \le 10^5$，$2 \le \sum n \le 2 \times 10^5$，$1 \le m,\sum m \le 2 \times 10^4$； - 对于任意的 $1 \le i \le n$，有 $0 \le a_i \le 2^{60} − 1$； - $\displaystyle \sum_{i=1}^{n} a_i \ge 1$。 | 测试点编号 | $n\le $ | $\sum n\le $ | $m\le$ | $\sum m\le$ | $a_i\le $ | 特殊性质 | | :--: | :--: | :--: | :--: | :--: | :--: | :--: | | $1$ | $2$ | $10^5$ | $10^4$ | $10^4$ | $2^{30}-1$ | 无 | | $2\sim 4$ | $5$ | $25$ | $10^4$ | $10^4$ | $2^{4}-1$ | B | | $5\sim 7$ | $6$ | $30$ | $10^4$ | $10^4$ | $2^{10}-1$ | B | | $8\sim 10$ | $10^5$ | $2\times 10^5$ | $10^4$ | $10^4$ | $2^{30}-1$ | A | | $11\sim 13$ | $10^5$ | $2\times 10^5$ | $1$ | $10^4$ | $2^{30}-1$ | B | | $14\sim 17$ | $10^3$ | $2\times 10^3$ | $10^2$ | $10^2$ | $2^{30}-1$ | B | | $18\sim 21$ | $10^5$ | $2\times 10^5$ | $10^4$ | $10^4$ | $2^{30}-1$ | B | | $22,23$ | $10^5$ | $2\times 10^5$ | $10^4$ | $10^4$ | $2^{30}-1$ | 无 | | $24,25$ | $10^5$ | $2\times 10^5$ | $2\times 10^4$ | $2\times 10^4$ | $2^{60}-1$ | 无 | - 特殊性质 A：对于任意的 $1\le i\le n$，$a_i$ 都是 $2$ 的非负整数幂次。 - 特殊性质 B：$a_1=0$。 ### 评分方式 对于每个测试点，如果你在所有测试数据中都正确地输出了小 w 需要的最小石子 数量（即输出格式中的 $k$），你将获得该测试点 $50\%$ 的分数。在此基础上，如果你在所有测试数据中都按照要求给出了方案，你将获得该测试点 $100\%$ 的分数。 注意，即使你只想回答小 w 需要的最小石子数量，也需要在回答的小 w 需要的最小石子数量后按照给定的格式输出方案数量以及**对应数量的，正确的，不重复的**方案。简单地输出 $m' = 0$ 即可完成这一点。