一般的位DP是数位，这个是排列位DP，位DP之后判解的字典序，经典问题……
具体看代码吧……：
#include<cstdio>
#include<cstring>
long long dp[2][25][25],tdp[2][25][25];
int f[25];
int main()
{
    dp[0][1][1]=dp[1][1][1]=1;
    for(int i=2;i<=20;i++)
    {
        for(int j=1;j<=i-1;j++) dp[i&1][i][j+1]=dp[i&1][i][j]+dp[i&1][i-1][j];
        for(int j=i-1;j>=0;j--) dp[~i&1][i][j]=dp[~i&1][i][j+1]+dp[~i&1][i-1][j];
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        long long k;
        scanf("%d%lld",&n,&k);
        memcpy(tdp,dp,sizeof(dp));
        int fl[2]={1,1};
        for(int i=n;i>=1;i--)
        {
            int j;
            for(j=1;k-dp[0][i][j]-dp[1][i][j]>0;j++) k-=dp[0][i][j]+dp[1][i][j];
            f[i]=j;
            if (!dp[0][i][j]) fl[0]=0;
            if (!dp[1][i][j]) fl[1]=0;
            for(j=f[i];j<=i-1;j++) dp[i&1][i-1][j]=0;
            for(j=1;j<=f[i]-1;j++) dp[~i&1][i-1][j]=0;
            if (!fl[0]) for(int j=1;j<=i-1;j++) dp[0][i-1][j]=0;
            if (!fl[1]) for(int j=1;j<=i-1;j++) dp[1][i-1][j]=0;
        }
        memcpy(dp,tdp,sizeof(dp));
        for(int i=2;i<=n;i++)
            for(int j=i-1;j>=1;j--)
                if (f[i]<=f[j]) f[j]++;
        printf("%d",f[n]);
        for(int i=n-1;i>=1;i--) printf(" %d",f[i]);
        puts("");
    }
}