按高位(1)、低位(0)的思想,进行计数DP。

$f_{i,j,k}$表示用$i$块长度不同的木板构成栅栏,且最左边的排在$j$位,$k$表示高位还是低位。

$f_{i,j,1}=\sum_{p=1}^{j-1}f_{i-1,p,0}\\f_{i,j,0}=\sum_{p=j}^{i-1}f_{i-1,p,1}$

之后试填每一位,先试填高位,再低位,因为下一位要反着来的。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define gc getchar()
#define ll long long
using namespace std;
const int mod=1e9+7;
template<class o> 
inline void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
bool v[21];ll f[21][21][2];
int main()
{
    f[1][1][0]=f[1][1][1]=1;//0 低位 1 高位 
    for(int i=2;i<=20;i++)
        for(int j=1;j<=i;j++)
        {
            for(int p=j;p<i;p++)//f[i][j][0]表示i块木板第一块排名为j且处于低位,后i-1个木板随机组成的合法总方案数 
                f[i][j][0]+=f[i-1][p][1];//排名为j+1(在i中的),顺位成为排名j的。 
            for(int p=j-1;p;p--)
                f[i][j][1]+=f[i-1][p][0];
        }
    int T;qr(T);
    while(T--)
    {
        int n;ll m;qr(n),qr(m);
        memset(v,1,n+1);
        int last,k;
        for(int i=1;i<=n;i++)
        {
            if(f[n][i][1]>=m)//第二位要小,因此先枚举1 
            {
                last=i;k=1;
                break;
            }
            else m-=f[n][i][1];
            if(f[n][i][0]>=m)
            {
                last=i;k=0;
                break;
            }
            else m-=f[n][i][0];
        }
        printf("%d",last);v[last]=0;
        for(int i=2;i<=n;i++)
        {
            k^=1;
            int j=0;//长度为len,排名为j 
            for(int len=1;len<=n;len++)
            {
                if(!v[len])continue;++j;
                if(k==0&&len<last||k==1&&len>last)
                {
                    if(f[n-i+1][j][k]>=m)
                    {
                        last=len;
                        break;
                    }
                    else m-=f[n-i+1][j][k]; 
                }
            }
            v[last]=0;printf(" %d",last);
        }
        puts("");
    }
    return 0;
}