题解：P7152 [USACO20DEC] Bovine Genetics G

· · 题解

Solution

一个比较显然的是，开始时的基因组序列的数量，就等于每种编辑后的基因组序列所有合法的划分方案数总和。

证明很简单，就是因为对于每一个开始时的基因组序列，有且仅有一种满足题意的划分方案。

那么考虑对于一个编辑后的基因组序列，使其一种合法划分方案需要满足什么性质。

首先要满足对于任意一段 \left[L, R\right] 中，不存在 i, j \in \left[L, R\right] 且 i \neq j，满足 s_i = s_j。其次，第 i 段的开头等于第 i + 1 段的结尾。

那么考虑 dp，设 f_{i, a, b, c} 表示前 i 个位置，最后一个段的结尾是 a，开头是 c，倒数第二段翻转后的开头是 b。转移是显然的。

时间复杂度 O(|\Sigma|^4n)。

:::success[AC Code]

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 1e5 + 5, mod = 1e9 + 7;
long long f[N][4][4][4];
char s[N];
int n, mp[200];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    mp['A'] = 0, mp['G'] = 1, mp['C'] = 2, mp['T'] = 3;
    cin >> s + 1;
    n = strlen(s + 1);
    For(i, 0, 3) {
        if (s[1] == '?') For(j, 0, 3) f[1][j][i][j] = 1;
        else f[1][mp[s[1]]][i][mp[s[1]]] = 1;
    }
    For(i, 2, n) For(j, 0, 3) {
        if (!(s[i] == '?' || mp[s[i]] == j)) continue;
        For(k, 0, 3) For(a, 0, 3) For(b, 0, 3) {
            if (j != k) f[i][j][a][b] = (f[i][j][a][b] + f[i - 1][k][a][b]) % mod;
            if (a == k) f[i][j][b][j] = (f[i][j][b][j] + f[i - 1][k][a][b]) % mod;
        }
    }
    long long ans = 0;
    For(i, 0, 3) {
        if (!(s[n] == '?' || mp[s[n]] == i)) continue;
        For(j, 0, 3) ans = (ans + f[n][i][i][j]) % mod;
    }
    cout << ans;
    return 0;
}

:::