DDOSvoid's Blog

bzoj 3864 Hero meet devil

发表于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

题目描述

给定一个长度为 $m$ 的只由 $ACTG$ 组成的字符串 $S$，求长度为 $n$ 的且与 $S$ 的 $lcs$ 为 $k$ 的只由 $ACTG$ 组成的字符串的数量，答案对 $10^9+7$ 取模，对于 $0$ 到 $k$ 都要输出答案

$m\le 15,n\le 10^3$

Solution

我们考虑求 $lcs$ 的 $dp$ 的转移过程，发现如果我们知道 $f[i][0\sim m]$ 那么就能推出 $f[i+1][0\sim m]$

且我们发现 $f[i][0\sim m]$ 可以用长度为 $m$ 的二进制串来表示，因为最多只会加 $m$ 次 $1$，所以我们考虑把这东西状压

我们令 $f[i][S]$ 表示长度为 $i$，$lcs$ 的 $dp$ 状态为 $S$ 的字符串数量，然后枚举下一位是什么进行转移即可，转移需要与第一维无关，所以可以提前预处理

时间复杂度 $O(4n2^m)$

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstring>
#define maxn 1010
#define maxm 20
using namespace std;

const int p = 1000000007;

int n, m, a[maxm];

char s[maxm]; 

int trans[1 << 15][4], ch[256], g[maxm], h[maxm];
void init_trans() {
    int M = (1 << m) - 1;
    for (int S = 0; S <= M; ++S) {
        for (int i = 1; i <= m; ++i) g[i] = g[i - 1] + (S >> i - 1 & 1);
        for (int k = 0; k < 4; ++k) {
            fill(h, h + maxm, 0); 
            for (int i = 1; i <= m; ++i) {
                if (a[i] == k) h[i] = g[i - 1] + 1;
                else h[i] = max(h[i - 1], g[i]); 
            } trans[S][k] = 0; 
            for (int i = 1; i <= m; ++i) 
                if (h[i] > h[i - 1]) trans[S][k] |= 1 << i - 1;
        }                                
    }
}

int f[maxn][1 << 15], ans[maxm];
void work() {
    cin >> s + 1 >> n; m = strlen(s + 1);
    for (int i = 1; i <= m; ++i) a[i] = ch[s[i]];
    int M = (1 << m) - 1; init_trans();
    fill(f[0], f[0] + maxn * (1 << 15), 0); f[0][0] = 1; 
    for (int i = 0; i < n; ++i)
        for (int S = 0; S <= M; ++S)
            for (int k = 0; k < 4; ++k)
                f[i + 1][trans[S][k]] = (f[i + 1][trans[S][k]] + f[i][S]) % p;
    fill(ans, ans + maxm, 0); 
    for (int S = 0; S <= M; ++S) ans[__builtin_popcount(S)] = (ans[__builtin_popcount(S)] + f[n][S]) % p;
    for (int i = 0; i <= m; ++i) cout << ans[i] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T; ch['A'] = 0; ch['T'] = 1; ch['C'] = 2; ch['G'] = 3;
    while (T--) work(); 
    return 0;
}