← 返回题目列表

Codeforces · 1279/E

E. 新年排列

中文机器翻译题面 查看原题

是的,我们未能为这个问题编造一个新年传说。

长度 $$$n$$$ 的排列是 $$$n$$$ 整数的数组,使得从 $$$1$$$ 到 $$$n$$$ 的每个整数在其中只出现一次。

如果$$$x = y$$$,或者$$$p_x = y$$$,或者$$$p_{p_x} = y$$$,等等,则排列$$$p$$$的元素$$$y$$$可以从元素$$$x$$$到达。

排列 $$$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$$$,找到第 $$$k$$$ 个(按字典顺序)长度为 $$$n$$$ 的良好排列。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

然后是测试用例。每个测试用例由一行包含两个整数 $$$n$$$ 和 $$$k$$$ 表示($$$1 \le n \le 50$$$, $$$1 \le k \le 10^{18}$$$)。

输出

对于每个测试用例,按如下方式打印答案:如果长度 $$$n$$$ 的良好排列数小于 $$$k$$$,则打印一个整数 $$$-1$$$;否则,打印 $$$n$$$ 元素上的第 $$$k$$$ 个好排列(按字典顺序)。

示例

输入 #1

5
3 3
5 15
4 13
6 8
4 2

输出 #1

2 1 3 
3 1 2 5 4 
-1
1 2 6 3 4 5 
1 2 4 3