A decorative fence 计数

【一句话题意】给n块长度为1~n的木板，组成一个长度为n的序列，满足相邻的木板都比自己长或短。方案按字典序排列。有多组询问，问当有ai块木板时，第bi号方案是什么。
ai<=20,bi<=2⁶³
【分析】类似于倍增dp的“拼凑”思想和手推康托展开时的方式，我们可以用“试填”的方式来确定第bi号方案中各个木板的长度。比如从小到大枚举，如果当第一块木板长为h时，N-1块木板的构成的方案数T大于bi，则第一块木板长度就应该是h；否则就应该是更长的，同时从bi中减去减去T。

为了加快“试填“的速度，我们要先预处理出所有的T值。这就需要把整个程序分成两个部分，dp预处理和“试填”（对询问的回答）。

dp部分定义f[i,j,k]表示用i块长度不同木板构成左边的序列，同时最左边的木块长度从小到大排为第j位，并且状态为k（k=0表示处于低位，k=1表示处在高位）的方案总数。转移方程为
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;f[i,j,0]=\Sigma^{i-1}_{p=1}f[i-1,p,1]$f[i,j,0]=Σp=1i−1​f[i−1,p,1]
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;f[i,j,1]=\Sigma^{i-1}_{p=1}f[i-1,p,0]$f[i,j,1]=Σp=1i−1​f[i−1,p,0]
同样的dp方式还可以用于离散化之后的问题，两者是等价的。

再是“试填”部分。特别的第一块木板既有可能是高位又有可能是低位，所以要特殊处理。其他的操作大致就是开头所讲。
【code】

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
LL n,m,T;
LL f[21][21][2];
void prework(){
	f[1][1][0]=f[1][1][1]=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]+=f[i-1][p][1];
			for(int p=1;p<j;p++)
				f[i][j][1]+=f[i-1][p][0];
		}
}
int main(){
	prework();
	cin>>T;
	while(T--){
		cin>>n>>m;
		bool used[21];
		memset(used,0,sizeof(used));
		int last,k;
		for(int j=1;j<=n;j++){
			if(f[n][j][1]>=m){
				last=j,k=1;
				break;
			}
			else m-=f[n][j][1];
			if(f[n][j][0]>=m){
				last=j,k=0;
				break;
			}
			else m-=f[n][j][0];
		}
		used[last]=1;
		printf("%d",last);
		for(int i=2;i<=n;i++){
			k^=1;
			int j=0;
			for(int len=1;len<=n;len++){
				if(used[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];
				}
			}
			used[last]=1;
			printf(" %d",last);
		}
		printf("\n");
	}
	return 0;
}