2831. 排列问题

【题目描述】

从前，有一个长度为n 的排列p

每次把排列的每个循环拿出来，写成标准循环，再做一次排序

循环：排列第i 位为p[i]，如果我们令i 点到p[i] 点连一条边，那么会形成若干个简单环，

每个简单环所有的p[i] 就构成一个循环

比如排列[4, 1, 6, 2, 5, 3]，有3 个循环(421)(63)(5)

每个循环从任意一个位置开始读都是一样的

比如(412) 也是(124),(241)。n 个循环就一共n 个表达法

我们规定一个标准循环是以循环内最大的数字开头

循环之间排序的关键字就是第一个数字的大小

如(421)(63)(5) 排序后是(421)(5)(63)

如果排序后的排列和原排列一样，那么就是可行排列

求n 个数的字典序第k 大的可行排列

【输入格式】

两个整数，n，k

保证k 在long long 范围内，保证有解

【输出格式】

n 个整数，表示满足条件的排列

【样例输入1】

4 3

【样例输出1】

1 3 2 4

【样例输入2】

10 1

【样例输出2】

1 2 3 4 5 6 7 8 9 10

【样例1解释】

n=4 时，字典序最小的三个可行排列依次是

1 2 3 4

1 2 4 3

1 3 2 4

【数据范围】

对于30% 的数据满足：1 ≤ n ≤ 10

对于100% 的数据满足，1 ≤ n ≤ 50

【来源】

qbxt 2017.10.4 t3