Description
给m个由A,C,G,T组成的DNA片段。现在你需要构造一些长度为n的字符串,使这些字符串完全被这些DNA片段覆盖。求构造方案数 $mod$ $1e9+9$ 。(DNA片段之间可以互相重叠)
长度 $n\leq1000$,片段个数 $m\leq10$,片段长度不大于10.
Sample Input & Output
6 2
CAT
TACT
2
(CATCAT和CATACT是可行的方案)
Solution
DNA间可以相互重叠,也就是匹配完某个DNA后,匹配下一个DNA时不一定会从头开始,而是从下一个DNA的某个前缀开始(这个前缀也是当前DNA的后缀)。为了表示这种关系,肯定会想到使用AC自动机来表示匹配的状态。
有了AC自动机,我们就可以把所有 $4^n$个字符串全部输入自动机,保证状态转移“合法”,统计出最终所有满足条件的状态就行了。现在我们要做的事情有三件:统计状态,判断状态转移是否合法,判断结果是否满足条件。我们一件一件来解决。
每个状态对应AC自动机上的一个节点,因此用一个dp[MAX_NODE]数组就可以存处于当前状态的方案数。每多放入一个字符,状态就会发生转移。理论上,当前字符数的状态只与上一字符数的状态有关,拿两个dp数组循环用就行了。但为了书写方便还是先定义成dp[MAXN][MAX_NODE],每次dp[i]由dp[i - 1]转移而来。
接下来来判断合法的状态。所有字符串都要被DNA覆盖,也就是在AC自动机上转移的时候,不能还没走到终点(DNA的结束点),就跑到另一个DNA字符串的前缀去了。只有当走到了终点的时候,才可以随意地走下一步(但是不能走回根)。
统计答案也很简单,只有那些DNA字符串结束点对应的状态才能被统计进最终答案。
根据以上分析可以写出以下式子:
$当j 为终点:$
$dp[i][j.next[k]] += dp[i - 1][j] (j.next[k] \neq root, k \in {A, C, G, T})$
$否则:$
$dp[i][j.next[k]] += dp[i - 1][j] (j.next[k] 不通过fail转移, k \in {A, C, G, T})$
提交上述代码会得到WA的结果。
考虑下面的例子: 3 3 ACCC A C。ACC显然是一个满足条件的字符串,但在自动机上,ACC却不是一个字符串的结尾,最终不会被统计答案。
那我是不是应该把字符串结尾通过fail传递下去呢?也就是说,只要一个字符串的后缀是某个更短的字符串的结尾,那这个字符串也被认为是满足条件的字符串。这样更不对了。考虑例子:2 2 ACC C,AC不满足条件,却因为有后缀C被错误地统计进了答案。
这个时候我们发现,怎么样都无法合理地表示答案。换句话说,现在这种定义状态的方式,会混淆一些本质不同的状态。在定义一个状态时,只是记录这个状态处于AC自动机的哪个节点是不够的,还得记录一些其它的东西。
从本质上思考,一个满足条件的字符串可以分成两部分,后一部分是最后一个被覆盖的DNA,前一部分是之前匹配好的一堆DNA。前一部分和后一部分可以重复。对于AC自动机上的一个状态,它的最长的DNA后缀是确定的,但是它之前已经被匹配好的长度是不确定的。而一旦我们确定了这两个值,我们只要判断之前匹配好的长度加上最长的DNA的后缀长度是否大于等于整个当前字符串的长度即可(等价于前一部分和后一部分正好拼接或覆盖)。我们在dp中还要加一维,记录某个状态被匹配的长度。顺便,为了之后的判断,AC自动机上每个节点的长度和最长DNA后缀的长度也要提前统计好来,后者可以通过fail边来转移。
和开始一样,继续解决三个问题:状态定义、答案判断、合法转移判断。
现在,$dp[i][j][k]$被定义为放第$i$个字符时,处于AC自动机上$j$号节点,在自动机前面已经匹配好了长度为$k$(而不是总长度已经匹配好了$k$)的方案数。$j.len,j.low$分别表示某个节点的长度,最长DNA后缀长度。
对于某个$j,k$,若$j.low + k \geq j.len$,则说明这个状态满足条件。最终$dp[n][j][k]$中满足条件的状态的dp值之和就是题目的答案。
转移时,我们不再死板通过判断一条边是否是通过fail转移的来判断这个转移合不合法。在当前一个非答案状态$i,j,k$上,对于下一状态$j.next$,只要$j.next.len + k > j.len$,就能保证在状态转移时中间没有“断掉”。下一个状态的最长匹配长度为$j.next.len + k - j.len - 1$。也就是说:
$dp[i + 1][j.next][j.next.len + k - j.len - 1] += dp[i][j][k]$
对于某个状态,如果它已经满足了被覆盖的条件,则下一状态的最长匹配长度一定是下一状态的长度减1(因为多出了一个新的未匹配字符),写成式子的话:
$dp[i + 1][j.next][j.next.len - 1] += dp[i][j][k]$
至此,题目顺利解完。dp数组是1000 100 10的,时间复杂度$O(n|str|\sum|str|)$
Review
题解部分应该是正常的思考过程,发现二维不够后用三维dp,这也是我写这题从WA改到AC的过程。
之前我一直以为,AC自动机中dp都很容易,只和处于哪个节点有关。看完题面后,我立马敲了一个二维dp出来,很快WA了。
在cf上对着样例调试多次后,我才发现怎么定义dp都不行。看了一眼题解,发现状态要多定义一维后,我重新地把题目考虑了一遍,定义出了新的状态。
后来状态转移我差不多写完了,交上去WA了一个大的样例。仔细思考过后我发现,非答案状态在转移时,它的最长匹配长度可能会变的,这一步转移需要认真考虑。改完这一处后总算AC了。
这题对我最大的启示和警示是,AC自动机的dp不一定都那么简单,很多时候但靠节点来定义状态是不够的。
在用dp时,一定要把状态的每一个变量的转移都考虑好。尤其是在重新定义了dp状态后,最好能完全从头推一遍递推关系。