8929: YACS - IAI 2023年7月月赛丙组 T5 —— 排列排序
[Creator : ]
Description
如果一个整数序列 $a_1,a_2,…,a_n$ 的每个数字都在 1 到 n 之间，且没有两个数字相等，则称这个序列为全排列。例如1,3,2 以及 4,3,2,1 都是全排列。
我们将所有的全排列排序，定义全排列 $a_1,a_2,…,a_n$ 与 $b_1,b_2,…,b_m$ 的排序先后关系如下：
我们将所有的全排列排序，定义全排列 $a_1,a_2,…,a_n$ 与 $b_1,b_2,…,b_m$ 的排序先后关系如下：
- 如果 n<m，则 a 序列更靠前
- 如果 n>m，则 b 序列更靠前
- 如果 n=m，则以字典序规则比较 a 序列与 b 序列，字典序更小的序列更靠前。
- 第 1 个全排列是 1
- 第 2 个全排列是 1 2
- 第 3 个全排列是 2 1
- 第 4 个全排列是 1 2 3
Input
单个整数：表示 k
Output
单独一行：表示第 k 个全排列
Constraints
30% 的数据 $1≤k≤1000$
60% 的数据 $1≤k≤1,000,000$
100% 的数据 $1≤k≤10^{15}$
60% 的数据 $1≤k≤1,000,000$
100% 的数据 $1≤k≤10^{15}$
Sample 1 Input
5
Sample 1 Output
1 3 2
Sample 2 Input
1
Sample 2 Output
1
Sample 3 Input
2
Sample 3 Output
1 2
3
2 1
HINT
相同题目：IAI月赛丙组。