【题解】【上海】【排列排序】

#include <bits/stdc++.h>
using namespace std;
long long k;
long long jc[105];
bool b[55];//标志该数是否被使用
int w;//答案是几个数字的全排列
void myprint(long long s,int step){//搜索
if (step==0) return;//所有数字完成，返回
long long x=(s-1)/jc[step-1]+1;//首位是第几个数字
for (int i=1;i<=w;i++){
if (b[i]==0){//没用过
x--;
if (x==0){
printf("%d ",i);//打印
b[i]=1;//标记已使用
break;
}
}
}
s%=jc[step-1];
if (s==0) s=jc[step-1];
myprint(s,step-1);
}
int main() {
cin>>k;
jc[0]=1;
long long sum=0;
for (int i=1;sum<=k;i++){
jc[i]=jc[i-1]*i;//求i的阶乘
sum+=jc[i];//求前i个数字组成的全排列一共多少个
w=i;//求出w
}
for (int i=1;i<w;i++){
k-=jc[i];//求出答案在w个数字组成的全排列中的序号
}
myprint(k,w);//搜索打印
return 0;
}