题目链接:CF553B Kyoya and Permutation ↗
该题解主要思路来源于 CodeForces 官方题解 ↗。
题目描述#
定义一个长度为的排列为仅由的元素组成,且每个元素恰好只出现次的序列。我们称数值在排列中的映射为。
Kyota Ootori 刚刚学习了排列的循环表示法。定义排列上的一个循环是一个由的一部分元素组成的序列,并且在这个序列中,任意一个元素在中的映射等于下一个元素(特别地,最后一个元素的映射等于第一个元素)。
显然,我们可以将一个排列划分成多个循环。例如可以被划分成,和三个循环。我们在每个循环周围加上括号,然后将它们连起来,得到的就是这个排列的循环表示法。例如的一种循环表示法是。
对于一个长度不为的排列,其循环表示法不是唯一的。为了使问题得到统一,我们定义一种标准循环表示法。即,对于每个循环,都将其最大值放在最前面,然后将这若干个循环按照最大值从小到大排列。这样,的标准循环表示法就是。
现在,Kyota 发现,如果我们去掉一个排列的标准循环表示法中的括号,我们将得到另一个排列。比如,由可以得到。
他还发现,将某些排列的标准循环表示法中的括号去除后,得到的排列和原排列是一样的。我们称这种排列为“好的排列”。他按字典序递增的顺序在纸上写下了长度为的所有好的排列,结果他的朋友 Tamaki Suoh 把这个列表搞丢了。Kyota 现在想要恢复这个列表。告诉你排列的长度以及,请你输出字典序从小到大第个好的排列。
输入格式#
第一行输入两个空格隔开的整数和。
输出格式#
一行,个空格隔开的整数,表示要求的排列。
样例1说明#
的标准循环表示法是,去掉括号后得到的是,和原来的排列一样。字典序比其小的两个满足要求的序列是和。
数据范围#
,。保证长度为的,第个好的排列一定存在。
解题思路#
提示:“好的排列”只能由的顺序排列通过以下操作得来:
- 在原排列上,选择若干个不相交的,长度为2的区间,然后翻转每个区间。
我们可以通过暴力打表或证明来发现这个规律。
证明如下:
我们考虑包含的那个循环。因为是最大值,因此这个循环一定是标准循环表示法中的最后一个,而且排在这个循环的最前面。
- 如果这个循环长度为,显然已经证完了(在原排列中一定是最后一个,而且在标准循环表示法中也是最后一个)。
- 如果这个循环长度为,那么显然构成这个循环的是和。
- 如果这个循环长度为,我们不妨假设这个循环是。那么,在原排列上,的位置上是,的位置上是,的位置上是。
- 如果令,那么在原排列上的顺序是,这是不可能与标准循环表示法相同的。
- 如果令,那么在原排列上的顺序是,这是也不可能与标准循环表示法相同的。
- 如果这个循环更长,那么其情况与长度为的类似,是不可能的。
既然我们已经证明了包含的循环要么是,要么是,那么我们可以去掉 或者 和,我们发现这变成了一个更小的问题,仍然符合上面证明出的规律。
然后我们来考虑长度为的“好的排列”一共有多少种。我们设一共有种。
对于,
对于,,因为和都是合法的。
对于,
-
假设包含的循环长度为,此时“好的排列”的个数就是长度为的“好的排列”的个数。
-
假设包含的循环长度为,那么排列的最后两项一定是,此时“好的排列”个数就是长度为的“好的排列”的个数。
规律马上就出来了!长度为的“好的排列”数量为斐波那契数列的第项(此处提到的数列开头几项是),记作。
那么如何构造第小呢?我们刚才是从后向前考虑。根据开头的“提示”,其实从前向后考虑是等价的。
考虑如果包含的循环长度为,那么这个排列以开头,随后是一个长度为的“好的排列”每一位都加上的结果。这样的“好的排列”数量为。如果小于等于,那么问题转化为构造长度为的,第小的“好的排列”,随后将这个排列每项增加,再在开头加一个。这可以递归实现。
如果包含的循环长度为,那么这个排列以开头,随后是一个长度为的“好的排列”每一位都加上的结果。如果大于,那么问题转化为构造长度为,第小的“好的排列”,随后将这个排列每项增加,再在开头加上。这也可以递归实现。
递归终止条件:
- 如果,那么构造出的排列一定是。
- 如果,那么构造出的排列一定是。
在具体实现时,我们可以使用一些比较优美的写法,以实现简洁的代码和优秀的复杂度(不过这题才,复杂度不是非常要紧),详见代码。
贴出代码
// 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;
}
cpp评测记录:R24368083 ↗