基因笑传之测测 Bovine
洛谷传送门：基因笑传之测测 Bovine
设给定字符串 \(s\) 长度为 \(n\)。
因为每一种划分的方式只需要对于每个子段取反串，而任意可能的原串必然存在一种合法的划分方式。因此合法的划分方式与可能的原串是一一对应的。
怎样才是合法的划分呢？
- 块内不能出现连续的相同字符，否则原串在这里就应该切开。
- 相邻两块合起来，其最左边和最右边的字符相等，否则划分不成立。
考虑线性 DP。
直接递推求合法的方案数是较为困难的，因此依靠一些“不完整”的划分，一点点拼到完整的合法划分进行转移。
设 \(f_{i,a,b,c}\) 为考虑到第 \(i\)，当前这一段的开头 \(a\)，目前拼的最后一个字符 \(b\)，上一段的开头 \(c\) 时的答案。最后答案为 \(\sum f_{n,a,b,a}\)。
枚举 \(c\) 为新加字符，\(b\) 为开头字符，\(a\) 为前一段开头，\(d\) 为原末尾字符。
当 \(c\ne d\)，即新加的字符与原来的字符不相等，不会出现块内连续相同字符时，有转移：
\[f_{i,c,b,a}\gets f_{i-1,d,b,a}
\]
当 \(a=d\)，即可以构成完整一段时，有转移：
\[f_{i,c,c,b}\gets f_{i-1,d,b,a}
\]
AC 代码
时间复杂度 \(\mathcal{O}(n|\Sigma|^4)\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MOD = 1e9 + 7, maxn = 1e5;
string gene = "ACGT", s; // 不是 AGCT
inline constexpr bool match(char c, int j)
{return (c == '?' || c == gene[j]);
}
ull ans = 0, f[maxn + 1][4][4][4]; // 当前结尾 当前开头 前一段开头
int main()
{cin.tie(nullptr)->sync_with_stdio(false);cin >> s;for (int c = 0; c < 4; c++){if (!match(s[0], c)) continue;for (int b = 0; b < 4; b++){f[0][c][c][b] = 1;}}// 能线性 DP 的主要原因是两个限制条件其实都是方便统计的// 一个只考虑连续字符，另一个只考虑段与段之间的开头和结尾是否相等for (int i = 1; i < s.size(); i++){for (int c = 0; c < 4; c++) // 新拼的字符{if (!match(s[i], c)) continue;for (int b = 0; b < 4; b++) // 开头的字符{for (int a = 0; a < 4; a++) // 前一段开头{for (int d = 0; d < 4; d++) // 当前段末尾字符{if (c != d) (f[i][c][b][a] += f[i - 1][d][b][a]) %= MOD; // 新拼一个字符 注意不能与前面的字符相同if (a == d) (f[i][c][c][b] += f[i - 1][d][b][a]) %= MOD; // 新开一段}}}}}for (int a = 0; a < 4; a++) for (int d = 0; d < 4; d++) (ans += f[s.size() - 1][a][d][a]) %= MOD; // 当前结尾 = 前一段开头cout << ans;return 0;
}
思路参考了 @OrangeRED 的 《题解：P7152 [USACO20DEC] Bovine Genetics G》。
创作声明
本文遵循 CC BY-NC-SA 4.0 协议。
保证本文未使用 GenAI 工具辅助创作。
转载例如下：
[原文](https://www.luogu.com.cn/article/mnhufn7g)作者为 [clx201022](https://www.luogu.com.cn/user/552688)，转载人保证会遵循 [CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans) 协议：以适当的方式署名，不以盈利为目的进行转载，并以相同方式共享。