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$个好的排列一定存在。

题目描述

Let's define the permutation of length $ n $ as an array $ p=[p_{1},p_{2},...,p_{n}] $ consisting of $ n $ distinct integers from range from $ 1 $ to $ n $ . We say that this permutation maps value $ 1 $ into the value $ p_{1} $ , value $ 2 $ into the value $ p_{2} $ and so on. Kyota Ootori has just learned about cyclic representation of a permutation. A cycle is a sequence of numbers such that each element of this sequence is being mapped into the next element of this sequence (and the last element of the cycle is being mapped into the first element of the cycle). The cyclic representation is a representation of $ p $ as a collection of cycles forming $ p $ . For example, permutation $ p=[4,1,6,2,5,3] $ has a cyclic representation that looks like $ (142)(36)(5) $ because 1 is replaced by 4, 4 is replaced by 2, 2 is replaced by 1, 3 and 6 are swapped, and 5 remains in place. Permutation may have several cyclic representations, so Kyoya defines the standard cyclic representation of a permutation as follows. First, reorder the elements within each cycle so the largest element is first. Then, reorder all of the cycles so they are sorted by their first element. For our example above, the standard cyclic representation of $ [4,1,6,2,5,3] $ is $ (421)(5)(63) $ . Now, Kyoya notices that if we drop the parenthesis in the standard cyclic representation, we get another permutation! For instance, $ [4,1,6,2,5,3] $ will become $ [4,2,1,5,6,3] $ . Kyoya notices that some permutations don't change after applying operation described above at all. He wrote all permutations of length $ n $ that do not change in a list in lexicographic order. Unfortunately, his friend Tamaki Suoh lost this list. Kyoya wishes to reproduce the list and he needs your help. Given the integers $ n $ and $ k $ , print the permutation that was $ k $ -th on Kyoya's list.

输入输出格式

输入格式


The first line will contain two integers $ n $ , $ k $ ( $ 1<=n<=50 $ , $ 1<=k<=min{10^{18},l} $ where $ l $ is the length of the Kyoya's list).

输出格式


Print $ n $ space-separated integers, representing the permutation that is the answer for the question.

输入输出样例

输入样例 #1

4 3

输出样例 #1

1 3 2 4

输入样例 #2

10 1

输出样例 #2

1 2 3 4 5 6 7 8 9 10

说明

The standard cycle representation is $ (1)(32)(4) $ , which after removing parenthesis gives us the original permutation. The first permutation on the list would be $ [1,2,3,4] $ , while the second permutation would be $ [1,2,4,3] $ .