「PA 2018 Final」Podobieństwo genetyczne 题解

核心思路

1. 问题转化

我们需要计算长度为 $m$ 的 DNA 序列 $w$ 的数量，其中 $w$ 要么同时是 $s_1$ 和 $s_2$ 的子序列，要么同时不是两者的子序列。

设：

• $U$ = 所有长度为 $m$ 的 DNA 序列总数 = $4^m$
• $A$ = $w$ 是 $s_1$ 子序列的序列集合
• $B$ = $w$ 是 $s_2$ 子序列的序列集合

根据容斥原理：

$$\text{答案} = |A \cap B| + |\overline{A} \cap \overline{B}| = |A \cap B| + (U - |A \cup B|) $$

由容斥原理：

$$|A \cup B| = |A| + |B| - |A \cap B|$$

所以：

$$\text{答案} = |A \cap B| + U - (|A| + |B| - |A \cap B|) = U - |A| - |B| + 2|A \cap B| $$

2. 关键观察

问题转化为计算：

• $|A|$ = $s_1$ 中长度为 $m$ 的不同子序列数量
• $|B|$ = $s_2$ 中长度为 $m$ 的不同子序列数量
• $|A \cap B|$ = 同时是 $s_1$ 和 $s_2$ 子序列的长度为 $m$ 的不同序列数量

3. 动态规划解法

由于 $m \leq 20$，我们可以使用状态压缩 DP。

定义 $dp1[i][mask]$ 表示在 $s_1$ 中，处理到位置 $i$ 时，当前子序列状态为 $mask$ 的方案数。

但更高效的方法是使用子序列自动机的思想。

4. 子序列自动机预处理

对于每个字符串 $s$，预处理 $next[i][c]$ 表示从位置 $i$ 开始，字符 $c$ 下一次出现的位置。

5. DP 状态设计

设 $f_s[pos]$ 表示在字符串 $s$ 中，从位置 $pos$ 开始可以形成的长度为 $m$ 的不同子序列数量。

转移：

$$f_s[pos] = \sum_{c \in \{\text{A,C,G,T}\}} f_s[next[pos][c] + 1] $$

6. 同时子序列计数

对于两个字符串，定义 $dp[pos1][pos2]$ 表示在 $s_1$ 中从 $pos1$ 开始，在 $s_2$ 中从 $pos2$ 开始，能形成的公共子序列数量。

转移：

$$dp[pos1][pos2] = \sum_{c} dp[next1[pos1][c] + 1][next2[pos2][c] + 1] $$

7. 记忆化搜索优化

由于 $m$ 较小，可以使用记忆化搜索，状态为 $(len, pos1, pos2)$，表示还需要选择 $len$ 个字符，当前在 $s_1$ 的 $pos1$ 位置和 $s_2$ 的 $pos2$ 位置。

算法实现

复杂度分析

• 预处理：$O(n \times |\Sigma|)$
• DP计算：$O(m \times n^2)$ 但通过记忆化优化
• 实际运行：由于 $m \leq 20$，状态数可控

关键优化

1. next数组预处理：快速找到下一个字符位置
2. 记忆化搜索：避免重复计算
3. 状态哈希：压缩状态空间