题意
对于一个长度为 $n$ 的字符串 $s$，我们建立一张 $n$ 个节点的带权无向图。每个节点代表一个后缀，两个节点之间的边权为这两个后缀的 LCP 长度。定义字符串 $s$ 的代价为对应图的最大生成树边权之和。
给定 $n, k$，求所有长度为 $n$，字符集为小写字母集合的字符串中，代价第 $k$ 小的是哪个。如果并列多个，任意输出一个。
$\sum n \le 4\times 10^5, k \le 10^{15}$。
题解
对于长度为 $n$ 的串，共有 $26^{n}$ 个，$n$ 稍微大一点的时候，这个数目就远大于 $k$ 了。因此我们猜测，当 $n$ 充分大的时候，第 $k$ 小和最小值应当相同。
先不急着思考怎么构造最小值，我们来分析一下“充分大”的界限在哪里：假设一个字符串出现了 $c$ 种不同字符，那么我们做单表替换，可以得到 $\frac{26!}{(26-c)!}$ 种不同的字符串。这个值关于 $c$ 单调递增，而当 $c\ge 12$ 时，这个值就已经超过 $10^{15}$ 了。因此，这告诉我们，“充分大”指的是 $n\ge 12$ 的情况。
而 $n\le 11$ 似乎是 trivial 的情况：我们考虑枚举 $\mathrm{Bell}(n)$ 中集合划分情况，每个集合内部的字符相同。那么方案数容易计算，查询的时候枚举一下答案即可。
这里我们顺便可以思考一下如何计算最大生成树：因为后缀的 LCP 在后缀数组上是一段区间的 height 最小值（设 height 数组为 $ht_i$），所以最大生成树必定是连接所有 $(sa_i, sa_{i + 1})$ 边，也即 $\sum ht_i$。根据经典结论，我们知道这就是 $\binom{n + 1}{2}-C$，其中 $C$ 表示 $s$ 的本质不同子串个数。因此计算代价迎刃而解。
接下来需要解决 $n\ge 12$ 的 case：求最小值也即最大化本质不同子串数量。先对答案的下界进行估计：枚举子串长度 $i$，那么至多有 $26^i$ 种不同子串，而 $s$ 种有 $n - i + 1$ 个这样的子串，因此答案 $\ge \sum\limits_{i = 1}^{n} \min(26 ^ i, n - i + 1)$。
这个下界取的到吗？直觉是猜测一定能取到。我们找到一个 $k$，使得 $26 ^ k + k - 1 \le n < 26 ^ {k + 1} + k$，那么目标就是所有长度 $< k$ 的都出现至少一次，而所有长度 $\ge k$ 的两两不同。
当 $n = 26 ^ k + k - 1$ 时，这是一个经典问题：我们考虑建 $26 ^ {k - 1}$ 个点，对于每个长度为 $k$ 的字符串，从前 $k - 1$ 个字符对应的点连一条边到后 $k - 1$ 个字符对应的点，构造一条欧拉回路即可不重不漏地遍历所有的子串。（这个序列又称为 De Bruijn 序列。）
当 $n > 26 ^ k + k - 1$ 时事情变得不太一样了。如果我们直接构造 $k + 1$ 的图，取长度为 $n$ 的前缀，这样不一定是最优的。我们还是希望在 $k$ 的图上找一条路径，然而直接找似乎并不简单。
考虑先拿出 $k - 1$ 的图，跑出一条欧拉回路。这条欧拉回路对应了 $k$ 的图上的一条哈密顿回路。我们删掉从全 $\texttt{a}$ 串出发的那条边，变成一条以全 $\texttt{a}$ 串结尾的路径。接下来以这个全 $\texttt{a}$ 串为起点，在 $k$ 的图上跑欧拉回路。我们为了使所有的子串不重复出现，还要把那条哈密顿路径上的对应边删掉。经过尝试可以发现一定能构造出长度为 $26^{k + 1} + k - 1$ 的路径（只有一个点的自环取不到），取长度为 $n$ 的前缀就必定最优了。
时间复杂度 $\mathcal O(\mathrm{Bell(m)}m^2+n|\Sigma|)$，其中 $m = 11$，$|\Sigma| = 26$。
赛后没多久就调出来了。太可惜了。
