P13445 [GCJ 2009 #3] Alphabetomials

众所周知，$4$ 次多项式与 $5$ 次多项式之间有着很大的区别。关于一般 $5$ 次多项式根不存在求根公式的问题，催生了著名的**Galois 理论**，不过据作者所知，这与我们这里的问题并无关系。 我们只考虑至多 $4$ 次的多元多项式，变量为 $26$ 个小写英文字母。例如，下面是一个这样的多项式： $\text{aber} + \text{aab} + \text{c}$ 给定一个字符串 $S$，我们可以用它来计算该多项式的值 $p(S)$，具体方法如下：将每个变量替换为该字母在 $S$ 中出现的次数。例如，对于上述多项式，若 $S = \text{"abracadabra edgar"}$，则其中有 $6$ 个 a，$2$ 个 b，$1$ 个 c，$1$ 个 e，$3$ 个 r。因此， $$ p(S) = 6 \times 2 \times 1 \times 3 + 6 \times 6 \times 2 + 1 = 109。 $$ 给定一个只包含小写字母且各不相同的单词字典，我们称一个字符串 $S$ 为 $d$-短语（$d$-phrase），如果 $$ S = "S_1\ S_2\ S_3\ \ldots\ S_d" $$ 其中 $S_i$ 是字典中的任意单词，$1 \leqslant i \leqslant d$。也就是说，$S$ 是由 $d$ 个字典单词用空格隔开拼成的。给定一个 $K \leqslant 10$，请你对每个 $1 \leqslant d \leqslant K$，计算所有 $d$-短语的 $p(S)$ 之和。由于答案可能很大，请输出对 $10009$ 取余后的结果。

第一行包含测试用例数量 $T$。接下来是 $T$ 组测试数据。每组测试数据格式如下： 第一行包含一个多元多项式表达式 $p$（格式见下文说明），后接一个空格和整数 $K$。 第二行是整数 $n$，表示字典中单词的数量。 接下来 $n$ 行，每行一个只含小写字母的单词。每个测试用例中不会有重复单词。 多项式总是写成若干项的和，每项是若干变量的乘积。$a^t$ 就写作 $t$ 个 a 连在一起。例如 $a^2b$ 写作 $aab$。每一项中的变量都按字典序非递减排列。

对于每个测试用例，输出一行，格式如下： Case #$X$: $sum_1\ sum_2\ \ldots\ sum_k$ 其中 $X$ 是测试编号（从 $1$ 开始），$sum_i$ 表示所有 $i$-短语的 $p(S)$ 之和，对 $10009$ 取余。

**限制条件** - $1 \leqslant T \leqslant 100$。 - 字符串 $p$ 由一个或多个项用加号连接，不以加号开头或结尾。每个 $p$ 最多有 $5$ 项。每项至少 $1$ 个、至多 $4$ 个小写字母，且字母按非递减字典序排列。同一多项式内不会有重复项。 - 每个单词非空，仅含小写英文字母，长度不超过 $50$。同一测试用例中不会有重复单词。 **小数据集** - 时间限制：3 秒 - $1 \leqslant n \leqslant 20$ - $1 \leqslant K \leqslant 5$ **大数据集** - 时间限制：6 秒 - $1 \leqslant n \leqslant 100$ - $1 \leqslant K \leqslant 10$ 翻译由 ChatGPT-4.1 完成。