P13259 [GCJ 2014 #2] Trie Sharding

一组字符串 $\mathbf{S}$ 可以被高效地存储在一个字典树（trie）中。字典树是一棵有根树，其中每个节点代表 $\mathbf{S}$ 中某个字符串的一个前缀，且不重复。 例如，如果 $\mathbf{S}$ 为 "AAA"、"AAB"、"AB" 和 "B"，那么对应的字典树将包含 $7$ 个节点，分别对应前缀：""、"A"、"AA"、"AAA"、"AAB"、"AB" 和 "B"。 我现在有一台服务器，用一个大的字典树来存储 $\mathbf{S}$。不幸的是，随着 $\mathbf{S}$ 的不断增大，我发现很难再将它完整地装进单台服务器的内存中。为了解决这个问题，我打算将 $\mathbf{S}$ 拆分并存储在 $\mathbf{N}$ 台不同的服务器上。具体来说，$\mathbf{S}$ 将被划分成若干个不相交的非空子集 $\mathbf{T}_1, \mathbf{T}_2, \ldots, \mathbf{T}_\mathbf{N}$，然后在每台服务器 $i$ 上构建仅包含 $\mathbf{T}_i$ 中字符串的字典树。 这种方式的缺点是：所有 $\mathbf{N}$ 个字典树中的节点总数可能会变多。更糟的是，我无法控制字符串是如何被划分到各个服务器上的！ 例如，如果 "AAA"、"AAB"、"AB" 和 "B" 被分配到两台服务器，其中一台存储 "AAA" 和 "B"，另一台存储 "AAB" 和 "AB"，那么第一台服务器的字典树需要 $5$ 个节点（""、"A"、"AA"、"AAA"、"B"），第二台服务器也需要 $5$ 个节点（""、"A"、"AA"、"AAB"、"AB"），总共就是 $10$ 个节点。而如果将所有字符串放到一台服务器上，只需要 $7$ 个节点。 现在，给定字符串集 $\mathbf{S}$ 和服务器数 $\mathbf{N}$，我希望你帮我计算以下两个问题： 1. 在最坏的划分方案下，所有服务器上字典树节点数的总和最多是多少？ 2. 有多少种划分方式能导致上述最大节点数？由于这个数可能非常大，请输出其对 $1,\!000,\!000,\!007$ 取模的结果。 注意：$\mathbf{N}$ 台服务器是有区别的——如果某种方案中一个字符串出现在 $\mathbf{T}_i$ 中，而另一种方案中它出现在 $\mathbf{T}_j$ 中（$i \neq j$），则这两种划分方式被认为是不同的。

输入的第一行是测试用例数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 个测试用例。 每个测试用例第一行包含两个用空格分隔的整数：字符串数量 $\mathbf{M}$ 和服务器数量 $\mathbf{N}$。接下来的 $\mathbf{M}$ 行，每行包含一个字符串，表示集合 $\mathbf{S}$ 中的一个元素。

对于每个测试用例，输出一行，格式为 `"Case #i: X Y"`，其中 $i$ 是测试用例编号（从 1 开始），$X$ 是最坏情况下所有服务器上的节点总数，$Y$ 是使得总节点数为 $X$ 的划分方案数量，模 $1,\!000,\!000,\!007$ 之后的结果。

**限制条件** - $1 \leq T \leq 100$ - 字符串集 $\mathbf{S}$ 中的字符串只包含大写英文字符 - $\mathbf{S}$ 中所有字符串互不相同 - $\mathbf{N} \leq \mathbf{M}$ ### Small 数据集（9 分） - 时间限制：~~60~~ 3 秒 - $1 \leq M \leq 8$ - $1 \leq N \leq 4$ - 每个字符串长度在 $1$ 到 $10$ 之间 ### Large 数据集（30 分） - 时间限制：~~120~~ 5 秒 - $1 \leq M \leq 1000$ - $1 \leq N \leq 100$ - 每个字符串长度在 $1$ 到 $100$ 之间 翻译由 ChatGPT-4o 完成