CF1310C Au Pont Rouge

VK 刚刚在圣彼得堡开设了第二个总部！其办公楼的一侧写有一个巨大的字符串 $s$。这一部分的办公室计划被分割成 $m$ 个会议室，分割方式要求会议室的墙壁严格位于楼体字母之间。显然，会议室的宽度不能为 $0$，但可以窄至仅包含一个字母。每个会议室将以其侧面对应的 $s$ 的子串命名。  对于每一种将 $s$ 分割成 $m$ 个会议室的方式，我们都为字典序最小的会议室名订购了一个测试标签。当这些标签送达时，它们被按字典序逆序排列。 请问，送达的第 $k$ 个标签上打印的会议室名是什么？

第一行包含三个整数 $n, m, k$，分别表示字符串 $s$ 的长度、计划分割的会议室数量，以及感兴趣的标签编号（$2 \le n \le 1\,000; 1 \le m \le 1\,000; 1 \le k \le 10^{18}$）。 第二行为长度为 $n$ 的字符串 $s$，仅包含小写英文字母。 保证对于给定的 $n, m, k$，存在至少 $k$ 种将 $s$ 分割成 $m$ 个子串的方式。

输出一行，表示送达的第 $k$ 个标签上打印的会议室名。

在第一个样例中，送达的标签依次为 "aba"、"ab"、"a"。 在第二个样例中，送达的标签共有 $3060$ 个。第一个标签为 "aupontrougevkof"，最后一个标签为 "a"。 由 ChatGPT 4.1 翻译