链接：
题意：给出一个 n ，求 1 ～ n 全排列的第 m 个排列情况
思路：经典逆康托展开，需要注意的时要在原来逆康托展开的模板上改动一些地方。
- 分析：已知 1 <= M <= 10000，10000 < 8!，根据逆康托展开的原理可以发现，A[n] * (n-1)! + A[n-1] * (n-2)! + A[n-2] * (n-3)! + ...... + A[2] * 1! + A[1] * 0! ，在前 n - 8 项之前，Ai == 0，所以每次都是取剩余排列中第 0 个最大元素，也就是 0 1 2 3 ... n - 9（ 从0开始 ），后面的项直接按照逆康托计算得到。
/************************************************************************* > File Name: hdu1027.cpp > Author: WArobot > Blog: http://www.cnblogs.com/WArobot/ > Created Time: 2017年05月18日 星期四 16时13分40秒 ************************************************************************/#includeusing namespace std;#define ll long long#define cls(x) memset(x,0,sizeof(x))const int MAX_N = 1010; // 排列长度const int MAX_C = 9; // 需要的最大阶乘N!ll fac[MAX_C]; // 初始化阶乘系数void init_fac(){ fac[1] = fac[0] = 1; for(int i = 2 ; i < MAX_C ; i ++) fac[i] = fac[i-1]*(ll)i;}// 寻找由1~n组成全排列按字典序排序后第x个排列void uCT(int n,int x){ bool vis[MAX_N]; cls(vis); int ans[MAX_N]; cls(ans); x--; int i , j; for(i = 0 ; i < n ; i++){ if( i >= n - 8 ){ int t = x/fac[n-i-1]; // 每次都寻找第t大的数 for(j = 0 ; j < n ; j++){ if(!vis[j]){ if( t == 0 ) break; t -- ; } } ans[i] = j; vis[j] = 1; x %= fac[n-i-1]; } else{ ans[i] = i; vis[i] = 1; } } for(i = 0 ; i < n-1 ; i++) printf("%d ",ans[i] + 1); printf("%d\n",ans[n-1]+1);}int main(){ int n , x; init_fac(); while(~scanf("%d%d",&n,&x)){ uCT(n,x); } return 0;}