题意：有一个字符集为 A, C, G, T 的字符串 $S$，问有多少个长度为 $n$ 的字符串 $T$ 满足 $\mathrm{LCS}(S, T) = i$。你需要输出所有 $i\in [0, |S|]$ 的答案。$|S|\leq 15$，$n\leq 1000$。
DP of DP 模板题。
首先考虑如果我们已经知道了 $T$，怎么计算 $\mathrm{LCS}(S, T)$。DP 过程不再赘述，这个 DP 过程结果可以由 $|S|$ 个数来代表，分别为每一个前缀和 $T$ 的 $\mathrm{LCS}$。
注意到一旦我们知道了这 $|S|$ 个数，前面的 $T$ 如何我们其实是不关心的。也就是说，我们可以把这 $|S|$ 个数变成状态，然后枚举 $T$ 的下一个字符，直接转移就可以做完。
但是注意到一个问题是这 $|S|$ 个数可能都比较大，不好压入状态。但是 $\mathrm{LCS}$ 的特殊性质告诉我们 $dp_i\leq dp_{i - 1} + 1$。因为一旦 $dp_i$ 匹配到了一个 $>dp_{i - 1} + 1$ 的东西，删掉最后一个数就可以得到 $dp_i - 1$ 更新 $dp_{i - 1}$。
这样我们就可以把差分数组压入状态，容易发现最多只有 $2 ^ {|S|}$ 种状态，就可以计算了，时间复杂度 $O(n 2^{|S|} \sum)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| void work()
{
std::cin >> s >> m;
n = strlen(s);
for (int sta = 0; sta < (1 << n); ++ sta)
for (int j = 0; j < 4; ++ j)
{
static int f[N], g[N];
f[0] = sta & 1;
for (int i = 1; i < n; ++ i) f[i] = f[i - 1] + (sta >> i & 1);
g[0] = f[0];
if (s[0] == ch[j]) chkmax(g[0], 1);
for (int i = 1; i < n; ++ i)
{
g[i] = g[i - 1], chkmax(g[i], f[i]);
if (s[i] == ch[j]) chkmax(g[i], f[i - 1] + 1);
}
int to = g[0];
for (int i = 1; i < n; ++ i)
if (g[i] != g[i - 1]) to |= 1 << i;
trs[sta][j] = to;
}
for (int sta = 0; sta < (1 << n); ++ sta) f[0][sta] = !sta;
for (int i = 1; i <= m; ++ i) {
for (int sta = 0; sta < (1 << n); ++ sta) f[i & 1][sta] = 0;
for (int sta = 0; sta < (1 << n); ++ sta)
for (int j = 0; j < 4; ++ j)
adj(f[i & 1][trs[sta][j]] += f[(i - 1) & 1][sta] - Mod);
}
static int ans[N + 1];
for (int i = 0; i <= n; ++ i) ans[i] = 0;
for (int s = 0; s < (1 << n); ++ s)
adj(ans[__builtin_popcount(s)] += f[m & 1][s] - Mod);
for (int i = 0; i <= n; ++ i) printf("%d\n", ans[i]);
}
|