题目描述

Scramble 教授在她正在审阅的一篇研究论文中注意到了一些拼写错误，但她阅读或理解这些单词时并没有困难。经过一些研究，她发现了一篇有趣的文章，如下所述：

根据一所英国大学的研究，单词中字母的顺序并不重要，唯一重要的是首字母和尾字母在正确的位置。其余字母可以完全打乱，你仍然可以毫无问题地阅读它。这是因为人脑不是逐个字母地阅读，而是将单词作为一个整体来阅读。

或者更确切地说……

Aoccdrnig to a study at an Elingsh uinertvis, it deosn't mttaer in waht oredr the ltteers in a wrod are, the olny iprmoetnt tiing is taht the frist and lsat ltteer be at the coreect pclae. The rset can be a toatl mses and you can sitll raed it wouthit a porblem. Tihs is bcuseae the huaamn mnid deos not raed ervey lleter by istlef, but the wrod as a whohle.

Scramble 教授希望进一步探索这一概念，并开始编译包含类似打乱单词的不同句子，以发送给一家知名刊物。不幸的是，教授键盘上的空格键坏了，因此她生成了一长串字符。她请你确定在她的字典中有多少个单词（至少一次）作为子串出现在这长串字符中，无论是原始形式还是打乱形式。（打乱形式由相同的字母集合组成，首字母和尾字母位置不变，其余字母可以任意排列。）

注意，一个字典单词可能在字符串中出现多次（但由于我们只关心它是否至少出现一次，因此只应计数一次）。例如，如果字典中有单词 this，那么会被计数的有效单词是 this（原始版本）和 tihs（打乱版本），而 tsih、siht 以及其他变体则无效，因为它们不以 t 开头且不以 s 结尾。此外，tis、tiss 和 thiss 不是打乱形式，因为它们不是原始字母集合的重排。

由于教授非常忙碌，她将这项任务交给了你——她最喜欢、最信任的研究助理。给定一个字典，你能计算出字典中有多少个单词至少一次以子串形式出现在教授的字符串中（无论是原始形式还是打乱形式）吗？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例包含三行。第一行包含一个整数 $L$。第二行包含 $L$ 个由小写英文字母组成的单词的列表；这些单词构成字典。第三行包含两个小写英文字母 $S_1$ 和 $S_2$，以及五个整数 $N$、$A$、$B$、$C$ 和 $D$。$S_1$ 和 $S_2$ 是教授字符串 $S$ 的前两个字符，$N$ 是 $S$ 的长度，其他四个整数是生成 $S$ 的字符时所使用的参数，生成方式如下：

首先定义 $\text{ord}(c)$ 为字符 $c$ 的十进制数值，$\text{char}(n)$ 为十进制数 $n$ 对应的字符。例如，$\text{ord}(\text{`a'}) = 97$，$\text{char}(97) = \text{`a'}$。其他转换可参考 ASCII 表。

现在，定义 $x_1 = \text{ord}(S_1)$，$x_2 = \text{ord}(S_2)$。然后，使用以下递推式生成 $i = 3$ 到 $N$ 的 $x_i$：

• $x_i = (A \times x_{i-1} + B \times x_{i-2} + C) \bmod D$。

对于所有 $i = 3$ 到 $N$，定义 $S_i = \text{char}(97 + (x_i \bmod 26))$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是字典中至少一次以（原始或打乱形式）作为给定字符串子串出现的单词数量。

1
5
axpaj apxaj dnrbt pjxdn abd
a a 50 1 1 1 30

Case #1: 4

提示

在样例 #1 中，使用生成方法得到的字符串 $S$ 为 aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt。

注意：对于本题的大数据集，我们不建议使用解释型/较慢的语言。

限制条件

$1 \le T \le 20$。

字典中没有两个单词相同。

字典中每个单词的长度在 $2$ 到 $10^5$ 之间（包含端点）。

字典中所有单词的长度之和不超过 $10^5$。

$S_1$ 和 $S_2$ 是小写英文字母。

$0 \le A \le 10^9$。

$0 \le B \le 10^9$。

$0 \le C \le 10^9$。

$1 \le D \le 10^9$。

小数据集（测试集 1 – 可见）

$1 \le L \le 1000$。

$2 \le N \le 1000$。

大数据集（测试集 2 – 隐藏）

$1 \le L \le 20000$。

$2 \le N \le 10^6$。

翻译由 DeepSeek V4 Pro 完成