题目地址：http://poj.org/problem?id=1037
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int UP=0,DOWN=1,maxn=20+5;
LL C[maxn][maxn][2],R;
//C[i][k][DOWN] 是S(i)中以第k短的木棒打头的DOWN方案数,
//C[i][k][UP] 是S(i)中以第k短的木棒打头的UP方案数,
// 第k短指i根中第k短
int N;
void DP(int n)
{memset(C,0,sizeof(C));C[1][1][DOWN]=C[1][1][UP]=1;for(int i=2;i<=n;i++)for(int k=1;k<=i;k++){for(int m=k;m<=i-1;m++)C[i][k][UP]+=C[i-1][m][DOWN];for(int m=1;m<=k-1;m++)C[i][k][DOWN]+=C[i-1][m][UP];}
}
void solve()
{bool used[maxn]={false};int seq[maxn];for(int i=1;i<=N;i++) //第几根木棍第一个 {int No=0,k; LL skipped=0;for(k=1;k<=N;k++) //第 {if(used[k]) continue;No++;if(i==1) skipped=C[N][No][DOWN]+C[N][No][UP];else {if(k>seq[i-1]&&(i<=2||seq[i-2]>seq[i-1]))skipped=C[N-i+1][No][DOWN];else if(k<seq[i-1]&&(i<=2||seq[i-2]<seq[i-1]))skipped=C[N-i+1][No][UP];}if(skipped>=R) break;else R-=skipped; }used[k]=true;seq[i]=k; }for(int i=1;i<=N;i++) cout<<seq[i]<<(" \n"[i==N]);
}
int main()
{int T; cin>>T;DP(20);while(T--){cin>>N>>R;solve();}
}