题意

给长度n的数列，1,2,..,n，按依次递增递减排序，求字典序第k小的排列。

题解

dp。

up[i][j]表示长度为j,以第i小开头前两个递增的排列有几种。

down[i][j]表示长度为j,以第i小开头前两个递减的排列有几种。

那么有\(down[i][j]=\sum_{k=1}^{k=j-1}up[k][j-1]\)

并且有\(down[1][1]=1\),\(up[i][j]=down[j-i+1][j]\)。

然后就可以递推了。

求第k小的排列，令s[i]=i(i=1,2,…n)，再令i为n到1,从小到大枚举未用过的i个数中第v小的，如果down[v][i]不比k小，说明后面是以第v小开头的长为i的开头递减排列，之后就要找这些排列中第k-down小的了。或判断up，根据标记的fup(表示之前是上升否)。输出s[v]，并移除s[v]。

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define N 21#define ll long longusing namespace std;int t,n;ll k;ll up[N][N],down[N][N];int s[N];void get(){    int fup,v=0;    for(int i=1;i<=n;i++)s[i]=i;    for(int i=n;i;i--){//剩下i个位置要放        if(i==n){            for(int j=1;j<=n;j++){//放第1小到第n小                if(k<=down[j][i]){//先考虑下降，因为下降则这个方案更小                    v=j;fup=0;break;//s[j]开头的够算，且是之后一个是上升                }                k-=down[j][i];//不够算，则找后面的第k-down大的方案。                if(k<=up[j][i]){                    v=j;fup=1;break;                }                k-=up[j][i];            }        }else{            if(fup){                for(int j=v;j<=i;j++){                    if(k<=down[j][i]){                        v=j;break;                    }                    k-=down[j][i];                }            }else{                for(int j=1;j