Permutation Chain

题意翻译

定义一个排列 $a$ （有 $n$ 个元素）的“固定性”为： $\displaystyle \sum_{i=1}^n [a[i]=i]$ 要求你建立一个排列的序列 $a_1,a_2,...,a_k$ （ $a[i]$ 为一个 $1$ ~ $n$ 的排列），使得： - $a_{i+1}$ 是由 $a_i$ 交换任意两个元素得到的 - 这些排列的"固定性"严格递减 输出任意一个最长的序列

题目描述

A permutation of length $ n $ is a sequence of integers from $ 1 $ to $ n $ such that each integer appears in it exactly once. Let the fixedness of a permutation $ p $ be the number of fixed points in it — the number of positions $ j $ such that $ p_j = j $ , where $ p_j $ is the $ j $ -th element of the permutation $ p $ . You are asked to build a sequence of permutations $ a_1, a_2, \dots $ , starting from the identity permutation (permutation $ a_1 = [1, 2, \dots, n] $ ). Let's call it a permutation chain. Thus, $ a_i $ is the $ i $ -th permutation of length $ n $ . For every $ i $ from $ 2 $ onwards, the permutation $ a_i $ should be obtained from the permutation $ a_{i-1} $ by swapping any two elements in it (not necessarily neighboring). The fixedness of the permutation $ a_i $ should be strictly lower than the fixedness of the permutation $ a_{i-1} $ . Consider some chains for $ n = 3 $ : - $ a_1 = [1, 2, 3] $ , $ a_2 = [1, 3, 2] $ — that is a valid chain of length $ 2 $ . From $ a_1 $ to $ a_2 $ , the elements on positions $ 2 $ and $ 3 $ get swapped, the fixedness decrease from $ 3 $ to $ 1 $ . - $ a_1 = [2, 1, 3] $ , $ a_2 = [3, 1, 2] $ — that is not a valid chain. The first permutation should always be $ [1, 2, 3] $ for $ n = 3 $ . - $ a_1 = [1, 2, 3] $ , $ a_2 = [1, 3, 2] $ , $ a_3 = [1, 2, 3] $ — that is not a valid chain. From $ a_2 $ to $ a_3 $ , the elements on positions $ 2 $ and $ 3 $ get swapped but the fixedness increase from $ 1 $ to $ 3 $ . - $ a_1 = [1, 2, 3] $ , $ a_2 = [3, 2, 1] $ , $ a_3 = [3, 1, 2] $ — that is a valid chain of length $ 3 $ . From $ a_1 $ to $ a_2 $ , the elements on positions $ 1 $ and $ 3 $ get swapped, the fixedness decrease from $ 3 $ to $ 1 $ . From $ a_2 $ to $ a_3 $ , the elements on positions $ 2 $ and $ 3 $ get swapped, the fixedness decrease from $ 1 $ to $ 0 $ . Find the longest permutation chain. If there are multiple longest answers, print any of them.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 99 $ ) — the number of testcases. The only line of each testcase contains a single integer $ n $ ( $ 2 \le n \le 100 $ ) — the required length of permutations in the chain.

输出格式

For each testcase, first, print the length of a permutation chain $ k $ . Then print $ k $ permutations $ a_1, a_2, \dots, a_k $ . $ a_1 $ should be an identity permutation of length $ n $ ( $ [1, 2, \dots, n] $ ). For each $ i $ from $ 2 $ to $ k $ , $ a_i $ should be obtained by swapping two elements in $ a_{i-1} $ . It should also have a strictly lower fixedness than $ a_{i-1} $ .

输入输出样例

输入样例 #1

2
2
3

输出样例 #1

2
1 2
2 1
3
1 2 3
3 2 1
3 1 2

**题目大意**：

定义一个长度为 $ n $ 的排列 $ p $ 的“固定性”为排列中固定点的数量，即位置 $ j $ 使得 $ p_j = j $ 的数量。

要求你建立一个排列序列 $ a_1, a_2, \dots $，从单位排列（$ a_1 = [1, 2, \dots, n] $）开始，称为排列链。对于每个 $ i $ 从 $ 2 $ 开始，排列 $ a_i $ 应该通过交换排列 $ a_{i-1} $ 中的任意两个元素得到，且 $ a_i $ 的固定性应该严格低于 $ a_{i-1} $ 的固定性。

找出最长的排列链。如果有多个最长链，输出其中任意一个。

**输入输出数据格式**：

**输入格式**：
- 第一行包含一个整数 $ 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] $）。对于每个 $ i $ 从 $ 2 $ 到 $ k $，$ a_i $ 应该通过交换 $ a_{i-1} $ 中的两个元素得到，且其固定性应严格低于 $ a_{i-1} $。**题目大意**： 定义一个长度为 $ n $ 的排列 $ p $ 的“固定性”为排列中固定点的数量，即位置 $ j $ 使得 $ p_j = j $ 的数量。 要求你建立一个排列序列 $ a_1, a_2, \dots $，从单位排列（$ a_1 = [1, 2, \dots, n] $）开始，称为排列链。对于每个 $ i $ 从 $ 2 $ 开始，排列 $ a_i $ 应该通过交换排列 $ a_{i-1} $ 中的任意两个元素得到，且 $ a_i $ 的固定性应该严格低于 $ a_{i-1} $ 的固定性。 找出最长的排列链。如果有多个最长链，输出其中任意一个。 **输入输出数据格式**： **输入格式**： - 第一行包含一个整数 $ 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] $）。对于每个 $ i $ 从 $ 2 $ 到 $ k $，$ a_i $ 应该通过交换 $ a_{i-1} $ 中的两个元素得到，且其固定性应严格低于 $ a_{i-1} $。