2019-ICPC-上海网络赛-F
2019-09-15 / Luo Jinrong   

F. Rhyme scheme

题意

一共有$n(1\leq n\leq 26)$行诗，这些诗句的韵脚（用$A$、$B$、$C$..表示）构成一个排列，这些排列的总数就是$bell$数$B_n$，把这些排列按字典序排序，求第$k$个。

做法

构造。首先我们易得第一个一定是$A$，那么下一位就可以填$A$或者$B$（对于任意一位，当前位能填的字母为$A$-之前出现过的$ascii$最大的字母+1）。举个例子，我们假设$n=3$的时候所有排列如下所示：

图中蓝色标记即为当前位填指定字母时的排列总数。

  • 第$1$位一定填$A$（下一位只能填$A$或$B$）是没有问题的，这时总数为$B_n$。
  • 然后我们接下来考虑第$2$位的情况：
    • 如果第二位填$A$（下一位只能填$A$或$B$），所以这个情况其实跟第一位考虑的情况是一样的，也就是这里的排列数量就是$n=2$时的排列总数，即$B_{n-1}$；
      • 第三位填$A$就是$n=1$的情况，即$B_{n-2}$；
      • 第三位填$B$，因为只能填$A$或$B$，所以这时的情况数就是总的情况-第三位填$A$的情况，即$B_{n-1}-B_{n-2}$。
    • 第二位填$B$（下一位可填$A$或$B$或$C$），因为只能填$A$或$B$，同上，情况数为$B_{n}-B_{n-1}$；
      • 第三位填$A$或$B$（下一位可填$A$或$B$或$C$），所以这个情况跟考虑上一位是一样的，情况数分别为$B_{n-1}-B_{n-2}$；
      • 第三位填$C$，因为只能填$A$或$B$或$C$，所以这时的情况数就是总的情况-第三位填$A$或$B$的情况，即$(B_n-B_{n-1})-2(B_{n-1}-B_{n-2})=B_n-3B_{n-1}+2B_{n-2}$。

也就是说我们每一位具体填某个字母时的方案数我们都可以根据公式得到，每填一位都会判断要求的第$K$个属于哪一块，每填一位都会分成类似上面的两个方向。然后我们就一位一位$dfs$搜索进行构造。因为公式会比较长，我做了一个预处理，将所有的$26$个公式中的系数存下来。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
#define FIN freopen("./F.in","r",stdin)
using namespace std;
typedef __int128 ll;
const ll maxn(1e5+5);
ll T,len,mat[30][30];
string ans;
__int128 k;
__int128 bell[]={1,1,2,5,15,52,203,877,4140,21147,115975,678570,4213597,27644437,190899322,1382958545,10480142147,82864869804,682076806159,5832742205057,51724158235372,474869816156751,4506715738447323,44152005855084346,445958869294805289,4638590332229999353,(__int128)(49631246523618756274)};
void scan(__int128 &x)//输入
{
    x = 0;
    int f = 1;
    char ch;
    if((ch = getchar()) == '-') f = -f;
    else x = x*10 + ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9')
        x = x*10 + ch-'0';
    x *= f;
}
void pre(){
	mat[1][1]=1;
	for(int i=2;i<=26;i++){
		for(int j=1;j<=i;j++){
			mat[i][j]=mat[i-1][j]-mat[i-1][j-1]*(i-1);
		}
	}
}
void dfs(ll lf,ll n,ll can,ll k){
	if(lf==len){
		return;
	}
	if(k==0){
		return;
	}
	if(k==1){
		ans+='A';
		dfs(lf+1,n-1,can,k);
		return;
	}
	ll all=0,next=0;
	for(int i=1;i<=can;i++){
		all+=mat[can][i]*bell[n+1-i];
	}
	for(int i=1;i<=can+1;i++){
		next+=mat[can+1][i]*bell[n+1-i];
	}
	if(k>all-next){
		ans+='A'+can;
		dfs(lf+1,n,can+1,k-(all-next));
	}else{
		ll base=(all-next)/can;
		ans+='A'+(k-1)/base;
		dfs(lf+1,n-1,can,(k-1)%base+1);
	}
}
int main(){
#ifndef ONLINE_JUDGE
	FIN;
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	pre();
	scan(T);
	for(int t=1;t<=T;t++){
		scan(len),scan(k);
		cout<<"Case #"<<t<<": ";
		ans.clear();
		ans+='A';
		if(len>1){
			dfs(1,len,1,k);
		}
		cout<<ans<<"\n";
	}
}

return 0;

本文链接：
https://luojinrong.github.io/2019/09/15/2019-ICPC-上海网络赛-F/