3.1 题目描述#

一个长度为n 的排列p[1..n] 把排列的每个循环拿出来，写成标准循环，再做一次排序 比如[4, 1, 6, 2, 5, 3]，有3 个循环(421)(63)(5) 其中第一个循环就是4 要到2 的位置，2 要到1 的位置，1 要到4 的位置

每个循环从任意一个位置开始读都是一样的 比如(412) 也是(124),(241)。n 个循环就一共n 个表达法 我们规定一个标准循环是以循环内最大的数字开头 循环之间排序的关键字就是第一个数字的大小 如(421)(63)(5) 排序后是(421)(5)(63) 如果排序后的拍列和原排列一样，那么就是可行排列 求n 个数的字典序第k 大的排列

3.2 输入格式#

两个整数，n，k 保证k 在long long 范围内，保证有解

3.3 输出格式#

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

3.4 Sample Input1#

4 3

3.5 Sample Output1#

1 3 2 4

3.6 Sample Input2#

10 1

3.7 Sample Output2#

1 2 3 4 5 6 7 8 9 10

3.8 数据范围及约定#

对于30% 的数据满足：1 <= n <= 10 对于100% 的数据满足，1 <= n <= 50

题解#

不要被卡读题

什么是循环

比如说 题目中的例子

4本应在的位置为2在的位置
2本应在的位置为1在的位置
1本应在的位置为4在的位置
这就是一个循环

然后先打一个表找规律

我们会惊讶的发现他好像和斐波那契有关

而且只会有相邻的两个数调换

然后按照规律跑就可以了

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;
#define LL long long
LL f[55], Sum[55];
int a[55];
bool mark[55];
int main()
{
    LL n, k;
    scanf("%lld%lld", &n, &k);
    f[0] = f[1] = f[2] = 1;
    Sum[0] = 1, Sum[1] = 2, Sum[2] = 3;
    for (int i = 3; i <= n; i++)
    {
        f[i] = f[i - 1] + f[i - 2];
        Sum[i] = Sum[i - 1] + f[i];
    }
    for (int i = 1; i <= n; i++)
        a[i] = i;
    while (k > 1)
    {
        int j = lower_bound(Sum, Sum + n + 1, k) - Sum -1;
        k -= Sum[j];
        mark[n - j - 1] = mark[n - j] = 1;
    }
    for (int i = 1; i <= n; i++)
        if (mark[i] && mark[i + 1])
            mark[i] = mark[i + 1] = 0, swap(a[i], a[i + 1]);
    for (int i = 1; i <= n; i++)
        printf("%d ", a[i]);
    //while (1)
    ;
}