CF1279E New Year Permutations

是的，我们没能为这个问题编造一个新年传说。 长度为 $n$ 的排列是一个包含 $n$ 个整数的数组，其中每个整数 $1$ 到 $n$ 恰好出现一次。 如果排列 $p$ 中的元素 $y$ 可以通过以下方式从元素 $x$ 到达，则称 $y$ 可以从 $x$ 到达：$x = y$，或者 $p_x = y$，或者 $p_{p_x} = y$，以此类推。 排列 $p$ 的分解定义如下：首先，我们有一个排列 $p$，其中所有元素都未被标记，并且有一个空列表 $l$。然后我们进行如下操作：只要 $p$ 中还有未被标记的元素，就找到最左边的未被标记元素，按它们在 $p$ 中出现的顺序列出所有可以从它到达的元素，标记这些元素，然后将这些元素的列表循环移动，使最大值出现在第一个位置，并将该列表作为 $l$ 的一个元素加入。所有元素都被标记后，$l$ 就是这种分解的结果。 例如，如果我们要构建 $p = [5, 4, 2, 3, 1, 7, 8, 6]$ 的分解，操作如下： 1. 初始时 $p = [5, 4, 2, 3, 1, 7, 8, 6]$（加粗的元素表示已标记），$l = []$； 2. 最左边未标记的元素是 $5$；从它可以到达 $5$ 和 $1$，所以要移动的列表是 $[5, 1]$；最大值已经在第一个位置，无需移动； 3. $p = [\textbf{5}, 4, 2, 3, \textbf{1}, 7, 8, 6]$，$l = [[5, 1]]$； 4. 最左边未标记的元素是 $4$，可到达的元素列表为 $[4, 2, 3]$；最大值已经在第一个位置，无需移动； 5. $p = [\textbf{5}, \textbf{4}, \textbf{2}, \textbf{3}, \textbf{1}, 7, 8, 6]$，$l = [[5, 1], [4, 2, 3]]$； 6. 最左边未标记的元素是 $7$，可到达的元素列表为 $[7, 8, 6]$；需要循环移动，变为 $[8, 6, 7]$； 7. $p = [\textbf{5}, \textbf{4}, \textbf{2}, \textbf{3}, \textbf{1}, \textbf{7}, \textbf{8}, \textbf{6}]$，$l = [[5, 1], [4, 2, 3], [8, 6, 7]]$； 8. 所有元素都已标记，$[[5, 1], [4, 2, 3], [8, 6, 7]]$ 就是分解的结果。 排列的新年变换定义如下：我们先构建该排列的分解；然后将分解中的所有列表按第一个元素升序排序（只交换列表，不改变列表内元素顺序）；最后将这些列表依次连接成一个新的排列。比如 $p = [5, 4, 2, 3, 1, 7, 8, 6]$ 的新年变换如下： 1. 分解为 $[[5, 1], [4, 2, 3], [8, 6, 7]]$； 2. 排序后变为 $[[4, 2, 3], [5, 1], [8, 6, 7]]$； 3. $[4, 2, 3, 5, 1, 8, 6, 7]$ 就是变换的结果。 如果一个排列经过新年变换后结果与自身相同，则称其为“好排列”。例如，$[4, 3, 1, 2, 8, 5, 6, 7]$ 是好排列；而 $[5, 4, 2, 3, 1, 7, 8, 6]$ 不是好排列，因为变换结果为 $[4, 2, 3, 5, 1, 8, 6, 7]$。 你的任务如下：给定 $n$ 和 $k$，求长度为 $n$ 的第 $k$ 个（按字典序）好排列。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例数量。 接下来每个测试用例一行，包含两个整数 $n$ 和 $k$（$1 \le n \le 50$，$1 \le k \le 10^{18}$）。

对于每个测试用例，按如下方式输出答案：如果长度为 $n$ 的好排列数量小于 $k$，输出一个整数 $-1$；否则，输出第 $k$ 个长度为 $n$ 的好排列（按字典序）。

由 ChatGPT 4.1 翻译