B. Kyoya and Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Let’s define the permutation of lengthnas an arrayp=[p1,p2,…,pn]consisting ofndistinct integers from range from1ton. We say that this permutation maps value1into the valuep1, value2into the valuep2and so on.
Kyota Ootori has just learned aboutcyclic representationof a permutation. Acycleis 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). Thecyclic representationis a representation ofpas a collection of cycles formingp. For example, permutationp=[4,1,6,2,5,3]has acyclic representationthat 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 thestandard cyclic representationof 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, thestandard cyclic representationof[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 lengthnthat 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 integersnandk, print the permutation that wask-th on Kyoya’s list.
Input
The first line will contain two integersn,k(1≤n≤50,1≤k≤min{1018,l}wherelis the length of the Kyoya’s list).
Output
Printnspace-separated integers, representing the permutation that is the answer for the question.
Sample test(s)
input
4 3
output
1 3 2 4
input
10 1
output
1 2 3 4 5 6 7 8 9 10
Note
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].
需要证明循环长度不会超过2，然后就能推出长度为i的这样的排列有fib[i]个，引用官方题解
Solving this requires making the observation that only swaps between adjacent elements are allowed, and all of these swaps must be disjoint. This can be discovered by writing a brute force program, or just noticing the pattern for smalln.
Here’s a proof for why this is. Consider the cycle that containsn. Sincenis the largest number, it must be the last cycle in the sequence, and it’s the first element of the sequence. If this cycle is length 1, then we’re obviously ok (we can always append(n)to the end). If the cycle is of length 2, we neednto be involved in a cycle withn-1. Lastly, if the cycle is of length 3 or more, we will see we run into a problem. We’ll only show this for a cycle of length 3 (though this argument does generalize to cycles of larger length). Let(nxy)be the cycle. So that means,nis replaced byx,xis replaced byyandyis replaced byn. So, in other words, the original permutation involving this cycle must look like
y x nnumber
However, we need it to look like(nxy)so this case is impossible.
So, once we know thatnis a in a cycle of length1or2, we can ignore the last 1 or 2 elements of the permutation and repeat our reasoning. Thus, the only valid cases are when we swap adjacent elements, and all swaps are disjoint. After making this observation, we can see the number of valid permutations of length n is fib(n+1). (to see this, write try writing a recurrence).
告诉自己，我这次失败了，重新开始吧!下次我会吸取教训，不让自己犯同样的错误的
