CF1716B Permutation Chain

一个长度为 $n$ 的排列是一个由 $1$ 到 $n$ 的整数构成的序列，其中每个整数恰好出现一次。 定义排列 $p$ 的“固定度”为其“定点”数量——即满足 $p_j = j$ 的位置 $j$ 的个数，其中 $p_j$ 表示排列 $p$ 的第 $j$ 个元素。 你需要从初始排列（即 $a_1 = [1, 2, \dots, n]$）开始，构造一个排列序列 $a_1, a_2, \dots$，我们称之为“排列链”。因此，$a_i$ 是第 $i$ 个长度为 $n$ 的排列。 对于每一个 $i \geq 2$，排列 $a_i$ 应通过交换 $a_{i-1}$ 中的任意两个元素（不要求相邻）得到。排列 $a_i$ 的固定度必须严格小于排列 $a_{i-1}$ 的固定度。 考虑 $n = 3$ 时的一些排列链示例： - $a_1 = [1, 2, 3]$，$a_2 = [1, 3, 2]$ —— 这是一个长度为 $2$ 的合法链。从 $a_1$ 到 $a_2$，第 $2$ 和第 $3$ 个元素交换，固定度从 $3$ 降到 $1$。 - $a_1 = [2, 1, 3]$，$a_2 = [3, 1, 2]$ —— 这不是一个合法链。对于 $n = 3$，第一个排列必须始终为 $[1, 2, 3]$。 - $a_1 = [1, 2, 3]$，$a_2 = [1, 3, 2]$，$a_3 = [1, 2, 3]$ —— 这不是一个合法链。从 $a_2$ 到 $a_3$，第 $2$ 和第 $3$ 个元素交换，但固定度从 $1$ 增加到 $3$。 - $a_1 = [1, 2, 3]$，$a_2 = [3, 2, 1]$，$a_3 = [3, 1, 2]$ —— 这是一个长度为 $3$ 的合法链。从 $a_1$ 到 $a_2$，第 $1$ 和第 $3$ 个元素交换，固定度从 $3$ 降到 $1$。从 $a_2$ 到 $a_3$，第 $2$ 和第 $3$ 个元素交换，固定度从 $1$ 降到 $0$。 请你求出最长的排列链。如果有多种最长方案，输出任意一种即可。

第一行包含一个整数 $t$（$1 \le t \le 99$），表示测试用例数量。 每个测试用例仅一行，包含一个整数 $n$（$2 \le n \le 100$），表示排列链中每个排列的长度。

对于每个测试用例，首先输出一个整数 $k$，表示排列链的长度。 接下来输出 $k$ 个排列 $a_1, a_2, \dots, a_k$。$a_1$ 必须是长度为 $n$ 的初始排列（$[1, 2, \dots, n]$）。对于每个 $2 \le i \le k$，$a_i$ 应通过交换 $a_{i-1}$ 中的两个元素得到，且其固定度严格小于 $a_{i-1}$ 的固定度。

由 ChatGPT 4.1 翻译