题目名称 3526. [USACO20Dec Gold]Bovine Genetics
输入输出 genetics.in/out
难度等级 ★★★
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试数据 20
题目来源 Gravatar数声风笛ovo 于2021-01-13加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:0, 提交:0, 通过率:0%
关于 Bovine Genetics 的近10条评论(全部评论)

3526. [USACO20Dec Gold]Bovine Genetics

★★★   输入文件:genetics.in   输出文件:genetics.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

Farmer John 在对他的奶牛进行基因组测序之后,他现在要进行基因组编辑了!我们知道,基因组可以用一个由 A、C、G、T 组成的字符串来表示。Farmer John 考虑的基因组的最大长度为 $10^5$。

Farmer John 从一个基因组开始,通过下列步骤对其进行编辑:


  1. 在所有连续相同字符之间的位置将当前基因组切开。
  2. 反转所有得到的子串。
  3. 按原先的顺序将反转的子串进行联结。

例如,如果 FJ 从基因组 AGGCTTT 开始,他会执行下列步骤:


  1. 在连续的 G 和 T 之间切开,得到 AG | GCT | T | T。
  2. 反转每一子串,得到 GA | TCG | T | T。
  3. 将这些子串联结起来,得到 GATCGTT。

不幸的是,在对基因组进行编辑之后,Farmer John 的计算机崩溃了,他丢失了他开始时的基因组序列。此外,编辑后的基因组的部分位置遭到了破坏,这些位置用问号代替。

给定编辑后的基因组序列,请帮助 FJ 求出可能的开始时的基因组序列的数量,对 $10^9+7$ 取模。

【输入格式】

一个非空字符串,其中每个字符为 A、G、C、T 和 ? 之一

【输出格式】

输出可能的开始时的基因组序列的数量模 $10^9+7$ 的结果。

【样例输入1】

?

【样例输出1】

4

【样例输入2】

GAT?GTT

【样例输出2】

3

【样例说明】

【样例 1 解释】

问号可以是 A、G、C 和 T 中的任意一个。

【样例 2 解释】

除了在之前说明过的 AGGCTTT 之外,还有两种可能的开始时的基因组。

AGGATTT -> AG | GAT | T | T -> GA | TAG | T | T -> GATAGTT

TAGGTTT -> TAG | GT | T | T -> GAT | TG | T | T -> GATTGTT

【数据规模与约定】

对于$ 20\% $的测试数据(测试点$ 1\sim4 $),满足基因组的长度不超过 $10$。

对于$ 55\% $的测试数据(测试点$ 1\sim11 $),满足基因组的长度不超过 $10^2$。

对于$ 100\% $的测试数据,均满足上文所给出的数据规模。

【来源】

USACO 十二月月赛 Gold 组