[洛谷题解] CF553B Kyoya and Permutation

题目描述

定义一个长度为 $n$ 的排列为仅由 $1..n$ 的元素组成，且每个元素恰好只出现 $1$ 次的序列。我们称数值 $i\ (1\leq i \leq |p|)$ 在排列 $p$ 中的映射为 $p_i$ 。

Kyota Ootori 刚刚学习了排列的循环表示法。定义排列 $p$ 上的一个循环是一个由 $1..n$ 的一部分元素组成的序列，并且在这个序列中，任意一个元素在 $p$ 中的映射等于下一个元素（特别地，最后一个元素的映射等于第一个元素）。

显然，我们可以将一个排列划分成多个循环。例如 $p=[4,1,6,2,5,3]$ 可以被划分成 $[1,4,2]$ ， $[3,6]$ 和 $[5]$ 三个循环。我们在每个循环周围加上括号，然后将它们连起来，得到的就是这个排列的循环表示法。例如 $[4,1,6,2,5,3]$ 的一种循环表示法是 $(1\ 4\ 2)(3\ 6)(5)$ 。

对于一个长度不为 $1$ 的排列，其循环表示法不是唯一的。为了使问题得到统一，我们定义一种标准循环表示法。即，对于每个循环，都将其最大值放在最前面，然后将这若干个循环按照最大值从小到大排列。这样， $[4,1,6,2,5,3]$ 的标准循环表示法就是 $(4\ 2\ 1)(5)(6\ 3)$ 。

现在，Kyota 发现，如果我们去掉一个排列的标准循环表示法中的括号，我们将得到另一个排列。比如，由 $[4,1,6,2,5,3]$ 可以得到 $[4,2,1,5,6,3]$ 。

他还发现，将某些排列的标准循环表示法中的括号去除后，得到的排列和原排列是一样的。我们称这种排列为“好的排列”。他按字典序递增的顺序在纸上写下了长度为 $n$ 的所有好的排列，结果他的朋友 Tamaki Suoh 把这个列表搞丢了。Kyota 现在想要恢复这个列表。告诉你排列的长度 $n$ 以及 $k$ ，请你输出字典序从小到大第 $k$ 个好的排列。

输入格式

第一行输入两个空格隔开的整数 $n$ 和 $k$ 。

输出格式

一行， $n$ 个空格隔开的整数，表示要求的排列。

样例1说明

$[1,3,2,4]$ 的标准循环表示法是 $(1)(3\ 2)(4)$ ，去掉括号后得到的是 $[1,3,2,4]$ ，和原来的排列一样。字典序比其小的两个满足要求的序列是 $[1,2,3,4]$ 和 $[1,2,4,3]$ 。

数据范围

$1 \leq n \leq 50$ ， $1 \leq k \leq 10^8$ 。保证长度为 $n$ 的，第 $k$ 个好的排列一定存在。

解题思路

提示：“好的排列”只能由 $1..n$ 的顺序排列通过以下操作得来：

在原排列上，选择若干个不相交的，长度为2的区间，然后翻转每个区间。

我们可以通过暴力打表或证明来发现这个规律。

证明如下：

我们考虑包含 $n$ 的那个循环。因为 $n$ 是最大值，因此这个循环一定是标准循环表示法中的最后一个，而且 $n$ 排在这个循环的最前面。

如果这个循环长度为 $1$ ，显然已经证完了（ $n$ 在原排列中一定是最后一个，而且在标准循环表示法中也是最后一个）。
如果这个循环长度为 $2$ ，那么显然构成这个循环的是 $n-1$ 和 $n$ 。
如果这个循环长度为3，我们不妨假设这个循环是(n\ x\ y)。那么，在原排列上，n的位置上是x，x的位置上是y，y的位置上是n。
- 如果令 $x\lt y$ ，那么在原排列上 $n,x,y$ 的顺序是 $y,n,x$ ，这是不可能与标准循环表示法 $(n\ x\ y)$ 相同的。
- 如果令 $x>y$ ，那么在原排列上 $n,x,y$ 的顺序是 $n,y,x$ ，这是也不可能与标准循环表示法 $(n\ x\ y)$ 相同的。
如果这个循环更长，那么其情况与长度为 $3$ 的类似，是不可能的。

既然我们已经证明了包含 $n$ 的循环要么是 $(n)$ ，要么是 $(n,n-1)$ ，那么我们可以去掉 $n$ 或者 $n$ 和 $n+1$ ，我们发现这变成了一个 $n$ 更小的问题，仍然符合上面证明出的规律。

然后我们来考虑长度为 $n$ 的“好的排列”一共有多少种。我们设一共有 $f(n)$ 种。

对于 $n=1$ ， $f(n) = 1$

对于 $n=2$ ， $f(n) = 2$ ，因为 $[1,2]$ 和 $[2,1]$ 都是合法的。

对于 $n>2$ ， $f(n) = f(n-2) + f(n-1)$

假设包含 $n$ 的循环长度为 $1$ ，此时“好的排列”的个数就是长度为 $n-1$ 的“好的排列”的个数。
假设包含 $n$ 的循环长度为 $2$ ，那么排列的最后两项一定是 $[n,n-1]$ ，此时“好的排列”个数就是长度为 $n-2$ 的“好的排列”的个数。

规律马上就出来了！长度为 $n$ 的“好的排列”数量为斐波那契数列的第 $n+1$ 项（此处提到的数列开头几项是 $1,1,2,3,5,8$ ），记作 $fib[n+1]$ 。

那么如何构造第 $k$ 小呢？我们刚才是从后向前考虑。根据开头的“提示”，其实从前向后考虑是等价的。

考虑如果包含 $1$ 的循环长度为 $1$ ，那么这个排列以 $1$ 开头，随后是一个长度为 $n-1$ 的“好的排列”每一位都加上 $1$ 的结果。这样的“好的排列”数量为 $fib[n]$ 。如果 $k$ 小于等于 $fib[n]$ ，那么问题转化为构造长度为 $n-1$ 的，第 $k$ 小的“好的排列”，随后将这个排列每项增加 $1$ ，再在开头加一个 $1$ 。这可以递归实现。

如果包含 $1$ 的循环长度为 $0$ ，那么这个排列以 $[2,1]$ 开头，随后是一个长度为 $n-2$ 的“好的排列”每一位都加上 $2$ 的结果。如果 $k$ 大于 $fib[n]$ ，那么问题转化为构造长度为 $n-2$ ，第 $k-fib[n]$ 小的“好的排列”，随后将这个排列每项增加 $2$ ，再在开头加上 $[2,1]$ 。这也可以递归实现。

递归终止条件：

如果 $n=1$ ，那么构造出的排列一定是 $[1]$ 。
如果 $n=0$ ，那么构造出的排列一定是 $[]$ 。

在具体实现时，我们可以使用一些比较优美的写法，以实现简洁的代码和优秀的复杂度（不过这题 $n$ 才 $50$ ，复杂度不是非常要紧），详见代码。

贴出代码

// status: [Accepted][he]
// oj:     [luogu]

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll

const int MAXN = 51;
// 读入的n和k
int n,k;
// 斐波那契数列预处理
int feiwu[MAXN];
// 构造排列时存入的数组
int arr[MAXN];

// 在arr[l..r]的空间中，构造l..r范围意义下，第rk小的“好的排列”
void buildArr(int l,int r,int rk) {
    // 待构造排列的长度
    int len = r-l+1;
    // 边界条件
    if(len==0) return;
    if(len==1) {arr[l] = l;return;}
    // 此时，第一项置为1，转化为构造n-1
    if(rk <= feiwu[len]) {
        arr[l] = l;
        arr[l+1] = l+1;
        buildArr(l+1,r,rk);
    }
    // 前两项为[2,1]，转化为构造n-2
    else {
        arr[l] = l+1;
        arr[l+1] = l;
        // 注意这里rk要减去长度为n-1的“好的排列”数量
        buildArr(l+2,r,rk-feiwu[len]);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>k;

    // 进行预处理
    feiwu[1] = feiwu[2] = 1;
    for(int i=3;i<=n;i++) {
        feiwu[i] = feiwu[i-1] + feiwu[i-2];
    }

    buildArr(1,n,k);

    for(int i=1;i<=n;i++) {
        if(i>1) cout<<" ";
        cout<<arr[i];
    }
    cout<<endl;
}

评测记录：R24368083