A decorative fence

在\(1\sim n\)的全排列\(\{a_i\}\)中，只有大小交错的（即任意一个位置i满足\(a_{i-1}<a_i>a_{i+1}ora_{i-1}>a_i<a_{i+1}\)）排列方案才是合法的，询问合法的第c个方案的全排列，\(n\leq 20,c\leq 2^{63}\)。

解

首先是求第几个方案，自然要用试填法，而排列问题不同于普通递推，因为一个数被放在这一个位置就不能在放了，但是注意到排列的一个性质，也就是注重大小关系，故可以考虑离散化递推。

为了试填，自然表现最左端填什么，也要表现序列的长度，为了能够维护序列的合法，不妨把最左端\(a_i>a_{i+1}\)记做，否则记做0,所以设\(f[i][j][k]\)表示长度为i的排列，最左端的数为第j大的数，状态为k的方案数，不难有

\[f[i][j][0]=\sum_{k=j}^{i-1}f[i-1][k][1]
\]

\[f[i][j][1]=\sum_{k=1}^{j-1}f[i-1][k][0]
\]

边界：\(f[1][1][0]=f[1][1][1]=1\)，其余为0

于是我们就可以直接利用方案数从小到大试填了，注意第一个位置状态可1,可0，优先填1即可。

参考代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#define il inline

#define ri register

#define ll long long

using namespace std;

bool used[21];

ll dp[21][21][2];

il void prepare();

int main(){

	int lsy;scanf("%d",&lsy),prepare();

	while(lsy--){

		int n,last;bool p;ll c;

		memset(used,0,sizeof(used));

		scanf("%d%lld",&n,&c);

		for(int i(1);i<=n;++i){

			if(dp[n][i][1]>=c){

				last=i,p=1;

				break;

			}

			else c-=dp[n][i][1];

			if(dp[n][i][0]>=c){

				last=i,p=0;

				break;

			}

			else c-=dp[n][i][0];

		}printf("%d ",last),used[last]|=true;

		for(int i(2),j,k;i<=n;++i){

			p^=true;

			for(j=1,k=0;j<=n;++j){

				if(used[j])continue;++k;

				if((p&&j>last)||(!p&&j<last))

					if(dp[n-i+1][k][p]>=c){

						last=j,used[j]|=true;

						break;

					}

					else c-=dp[n-i+1][k][p];

			}printf("%d ",last);

		}putchar('\n');

	}

	return 0;

}

il void prepare(){

	dp[1][1][0]=dp[1][1][1]=1;

	for(int i(2),j,k;i<=20;++i)

		for(j=1;j<=i;++j){

			for(k=j;k<i;++k)dp[i][j][0]+=dp[i-1][k][1];

			for(k=1;k<j;++k)dp[i][j][1]+=dp[i-1][k][0];

		}

}

巴特西

A decorative fence

解

最新文章

热门文章