Rhyme scheme（2019上海网络赛）（贝尔数+dp+dfs）

Rhyme scheme

赛后：原来就这么个简单题！

题意：给定 $n$n和 $k$k，求大小为 $n$n的集合的第 $k$k小字典序划分（输出格式见下方题面）
思路：

1. 令大小为 $i$i的集合在选择第 $j$j个位置时左边已经有 $k$k个集合为 $dp\left[i\right]\left[j\right]\left[k\right]$dp[i][j][k]
2. 则 $dp$dp的转移方程为： $dp\left[i\right]\left[j\right]\left[k\right]=dp\left[i\right][j+1][k+1]+k\ast dp\left[i\right][j+1]\left[k\right]$dp[i][j][k]=dp[i][j+1][k+1]+k∗dp[i][j+1][k]；对 $26$26中 $i$i分别倒过来 $dp$dp，同时要记得先初始化 $dp\left[i\right][i+1]\left[k\right]=1$dp[i][i+1][k]=1（也就是所有位置的所属集合都确定了）
3. 算出所有 $dp$dp值后，对给定的 $n,k$n,k进行 $dfs$dfs划分，找到 $k$k所代表的的答案即可
4. 最后：由于贝尔数在第 $26$26项时爆 $longlong$longlong了，因此 $dp,k$dp,k都需要用 $int128$int128(贝尔数前 $26$26项)

题面描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

__int128 f[27][28][28], k;
char l[50], ans[50];
int n;

void dfs(int cur, int mx) {
	if(cur>n) return;
	if(k>mx*f[n][cur+1][mx]) {
		k-=mx*f[n][cur+1][mx];
		ans[cur-1]='A'+mx;
		dfs(cur+1,mx+1);
		return;
	}
	ans[cur-1]='A'+(k-1)/f[n][cur+1][mx];
	k=(k-1)%f[n][cur+1][mx]+1;
	dfs(cur+1,mx);
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
	for(int i=1; i<=26; ++i) {
		for(int k=1; k<=i; ++k) f[i][i+1][k]=1;
		for(int j=i; j; --j)
			for(int k=j-1; k>=0; --k)
				f[i][j][k]=f[i][j+1][k+1]+k*f[i][j+1][k];
	}
	int T=read(), t=0;
	while(T--) {
		scanf("%d%s", &n, l); k=0;
		for(int i=0; l[i]; ++i) k=10*k+l[i]-'0';
		dfs(1,0);
		printf("Case #%d: %s\n", ++t, ans);
		for(int i=0; ans[i]; ans[i++]=0);
	}
}