P12551 [UOI 2025] Simple Task

我们称一个非空的正整数序列为*奇异*序列，如果其元素之和是一个质数。 给定一个长度为 $n$ 的数组 $a$，**其中的元素均为质数**。同时给定一个整数 $k$。 请将数组 $a$ 分割成 $k$ 个**非空**子序列$^1$，使得： - 数组 $a$ 的每个元素恰好属于其中一个子序列； - 在这些子序列中，*奇异*序列的数量尽可能少。 本题每个测试包含多组输入数据，你需要分别独立处理每组数据。 **注意：本题没有"无额外限制"的评分 Subtask。**

第一行包含一个整数 $T$ $(1\le T\le 10^5)$ —— 输入数据的组数。接下来是各组数据的描述。 每组数据的第一行包含两个整数 $n$, $k$ $(1 \le k \le n \le 10^5)$ —— 数组 $a$ 的长度和需要分割成的子序列数量。 每组数据的第二行包含 $n$ 个质数 $a_1, a_2, \ldots, a_n$ $(2\le a_i\le 10^5, a_i\le a_{i+1})$ —— 数组 $a$ 的元素。 保证单个测试中所有数据的 $n$ 之和不超过 $10^5$。

对于每组数据，按照以下格式输出最优分割方案： - 第一行输出一个整数 $m$ —— 分割后得到的*奇异*序列数量； - 接下来的 $k$ 行，每行输出整数 $s_i$ 和 $b_1, b_2, \ldots, b_{s_i}$ $(1\le s_i\le n)$ —— 对应子序列的元素个数及其元素。 子序列及其元素的输出顺序可以任意。 如果存在多个正确答案，输出任意一个即可。

$^1$ 序列 $c$ 称为数组 $b$ 的子序列，如果可以通过从数组 $b$ 中删除若干元素（可能为零个）来得到序列 $c$。 ### 评分标准 - （$2$ 分）：$T \leq 20$，$k=1$； - （$5$ 分）：$n \leq 4$，所有 $1\le i\le n$ 满足 $a_i \leq 10^4$； - （$8$ 分）：$T \leq 20$，$n \leq 10$，所有 $1\le i\le n$ 满足 $a_i \leq 10^4$； - （$4$ 分）：$n$ 为偶数，所有 $1\le i\le n$ 满足 $a_i > 2$； - （$18$ 分）：$n$ 为奇数，所有 $1\le i\le n$ 满足 $a_i > 2$； - （$10$ 分）：$2\cdot k \ge n + 1$； - （$29$ 分）：$n$ 为偶数； - （$24$ 分）：$n$ 为奇数。 翻译由 DeepSeek V3 完成