CF2157H.Keygen 3

Trey Frey - Refresh

⠀

一个长度为 $n$ 的排列 $^{\ast}$ 被称为合法的，如果它同时满足以下两个性质：

• 它是一个双调排列 $^{\dagger}$；
• 恰好有 $m$ 个子集是一个循环节 $^{\ddagger}$。

记满足上述条件的排列有 $k$ 个。你的任务是找到并输出 $\min(k, 2000)$ 个这样的排列作为示例。

$^{\dagger}$ 一个排列 $p_1, p_2, \ldots, p_n$ 称为双调的，如果存在一个下标 $i$（$1 \leq i \leq n$），使得

• 对于 $2 \leq j \leq i$，有 $p_{j-1} \leq p_j$；
• 对于 $i \leq j \leq n-1$，有 $p_j \geq p_{j+1}$。

$^{\ddagger}$ 一个子集 $C \subseteq \{1, 2, \ldots, n\}$ 被称为循环节，如果它满足以下条件：

• $C$ 非空；
• 如果 $x \in C$，则 $p_x \in C$；
• $C$ 是极小的，即不存在满足 $C' \subset C$ 的循环节 $C'$。

$^{\ast}$ 长度为 $n$ 的排列指的是 $1$ 到 $n$ 的全排列，即由 $n$ 个两两不同的 $1$ 到 $n$ 的整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是（$n=3$ 时出现了 $4$）。

输入包含一行，包含两个整数 $n, m$（$1 \leq m \leq n \leq 100$），分别表示排列的长度和要求循环节的个数。

输出第一行为一个整数 $r$，表示你将要输出的排列数量。注意 $r=\min(k, 2000)$，$k$ 定义见题目说明。

接下来输出 $r$ 行，每行一个长度为 $n$ 的双调排列，其循环节数量为 $m$。

在样例中，有 $9$ 个合法排列（即长度为 $6$ 的双调排列且循环节为 $3$）。例如，$[3, 5, 6, 4, 2, 1]$ 是双调的（在上述定义中，$i=3$），它有 $3$ 个循环节：$\{1, 3, 6\}$，$\{2, 5\}$，$\{4\}$。因此你需要输出 $r = \min(9, 2000) = 9$ 个这样的排列。

由 ChatGPT 5 翻译