CodeForces - 553B (数学题

题意：把一个排列表示成若干环，这些环内的元素逆序排列，各个环以最大元素为关键字顺序排列，求使排列的环表示和原排列一样的第k个排列。

思路：斐波那契数列，因为必须是两位相邻，所以输出也不难。

#include<iostream>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<queue>
#include<stack>
#include<functional>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxv=1005;
const ll mod=1e9+7;
ll fei[60];
vector<int> getans(int n,int add,ll k){
vector<int> ans,ans2;
if(n<=0) return ans;
if(fei[n-1]>=k){
ans.pb(1+add);
ans2=getans(n-1,add+1,k);
}else{
ans.pb(2+add);ans.pb(1+add);
ans2=getans(n-2,add+2,k-fei[n-1]);
}
for(int i=0;i<ans2.size();i++) ans.pb(ans2[i]);
return ans;
}
ll n,k;
int main(){
freopen("/home/files/CppFiles/in","r",stdin);
fei[0]=fei[1]=1;
for(int i=2;i<55;i++) fei[i]=fei[i-1]+fei[i-2];
while(cin>>n>>k){
vector<int> out=getans(n,0,k);
for(int i=0;i<out.size();i++){
cout<<out[i]<<" ";
}
cout<<endl;
}
return 0;
}