CF1183H Subsequences (hard version)

简单版和困难版的唯一区别在于约束条件。 子序列是指可以通过从另一个字符串中删除若干（可以为零）字符且不改变剩余字符顺序得到的字符串。被删除的字符不要求连续，中间可以有任意间隔。例如，对于字符串 "abaca"，以下字符串是它的子序列："abaca"、"aba"、"aaa"、"a" 和 ""（空串）。但以下字符串不是它的子序列："aabaca"、"cb" 和 "bcaa"。 给定一个由 $n$ 个小写拉丁字母组成的字符串 $s$。 每次操作，你可以取 $s$ 的任意一个子序列 $t$，并将其加入集合 $S$。集合 $S$ 不能包含重复的元素。每次操作的代价为 $n - |t|$，其中 $|t|$ 表示所添加子序列的长度（即代价等于被删除字符的数量）。 你的任务是求出获得大小为 $k$ 的集合 $S$ 的最小总代价，或者报告无法做到。

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 100, 1 \le k \le 10^{12}$），分别表示字符串的长度和集合的大小。 第二行包含一个由 $n$ 个小写拉丁字母组成的字符串 $s$。

输出一个整数——如果无法获得大小为 $k$ 的集合 $S$，输出 $-1$。否则，输出获得集合 $S$ 的最小总代价。

在第一个样例中，可以生成 $S = \{\text{"asdf"}, \text{"asd"}, \text{"adf"}, \text{"asf"}, \text{"sdf"}\}$。$S$ 中第一个元素的代价为 $0$，其余元素的代价为 $1$。所以 $S$ 的总代价为 $4$。 由 ChatGPT 4.1 翻译