SP8769 STRDIST2 - String distance

Prof.XYZ 是一位研究 DNA 序列分析的专家。他的一项研究是关于 DNA 序列的条形码编码。当前的任务是，在给定两个 DNA 序列的情况下，寻找到一种高效计算它们相似性的方法。形式上，DNA 序列是一个长度为 $N$ 的字符串 $S$，其中每个字符都来自词汇表 $\sum$ 中的特定符号。我们定义字符串 $S$ 的 $m$-扰动集 $\Delta(S, m)$，即通过更改 $S$ 中最多 $m$ 个字符（$m \leq N$）而得到的所有可能字符串的集合。换句话说，$\Delta(S, m)$ 包含所有与 $S$ 有汉明距离至多为 $m$ 的字符串集合。 Prof.XYZ 定义长度为 $N$ 的两个字符串 $S1$ 和 $S2$ 的 $(m1, m2)$ 相似性为 $\Delta(S1, m1)$ 与 $\Delta(S2, m2)$ 的交集中字符串的数量。很明显，这一交集的大小仅依赖于 $S1$ 和 $S2$ 之间的汉明距离，而非这两个字符串的具体值。换句话说，$|\Delta(S1, m1) \cap \Delta(S2, m2)|$ 的结果仅是 $N$、汉明距离 $H(S1, S2)$、$m1$、$m2$ 以及字母表大小 $|\sum|$ 的函数。因此，你的任务是编写一个程序，根据给定的 $N$、$m1$、$m2$、$H(S1, S2)$ 和 $|\sum|$ 计算交集的大小。因结果可能非常庞大，请以 $1000000007$ 取模的方式输出答案。 ### 输入格式 第一行输入包含测试用例的数量 $T$（最多 50 个）。接下来的每个测试用例由 5 个整数组成： 1. $N$：两个字符串的长度，满足 $1 \leq N \leq 1000$。 2. $m1$：第一个字符串中允许修改的字符数，满足 $0 \leq m1 \leq \min(100, N/2)$。 3. $m2$：第二个字符串中允许修改的字符数，满足 $0 \leq m2 \leq \min(100, N/2)$。 4. $H(S1, S2)$：两个字符串之间的汉明距离，满足 $0 \leq H \leq \min(100, N/2)$。 5. $|\sum|$：词汇表的大小，满足 $2 \leq |\sum| \leq 1000000$。 ### 输出格式 对于每个测试用例，输出交集的大小，对 $1000000007$ 取模的结果。 ### 示例 ``` 输入： 3 6 1 2 2 2 10 2 2 3 5 20 3 4 5 7 输出： 3 24 1925 解释（第一个测试用例）： 字符串的长度是 6，我们可以在第一个字符串中最多改变一个符号，在第二个字符串中最多改变两个符号。设第一个字符串为 $S1=000000$，第二个字符串为 $S2=000011$，它们的汉明距离为 2。$\Delta(S1, 1)$ 的集合为 {000000, 000001, 000010, 000100, 001000, 010000, 100000}。在不完全枚举 $\Delta(S2, 2)$ 的情况下，我们看到只有 {000000, 000001, 000010} 属于两者的交集。因此，$|\Delta(S1, m1) \cap \Delta(S2, m2)| = 3$。 ``` **本翻译由 AI 自动生成**

无

无