按高位(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;
}
最后一次更新于2019-11-02
0 条评论