BZOJ1030 文本生成器 && POJ2778 DNA Sequence AC自动机

发布于 2017-07-09  2.28k 次阅读


先上题目:

[toggle hide="yes" title="BZOJ1030 文本生成器" color=""]

Description

JSOI交给队员ZYX一个任务,编制一个称之为“文本生成器”的电脑软件:该软件的使用者是一些低幼人群,他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章—— 也就是说,生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词,那么我们说这篇文章是可读的(我们称文章a包含单词b,当且仅当单词b是文章a的子串)。但是,即使按照这样的标准,使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的。 ZYX需要指出GW文本生成器 v6生成的所有文本中可读文本的数量,以便能够成功获得v7更新版。你能帮助他吗?

Input

输入文件的第一行包含两个正整数,分别是使用者了解的单词总数N (<= 60),GW文本生成器 v6生成的文本固定长度M;以下N行,每一行包含一个使用者了解的单词。 这里所有单词及文本的长度不会超过100,并且只可能包含英文大写字母A..Z  。

Output

一个整数,表示可能的文章总数。只需要知道结果模10007的值。

Sample Input

       2 2
A
B

Sample Output

       100

[/toggle]

[toggle hide="yes" title="POJ2778 DNA Sequence" color=""]

Description

It's well known that DNA Sequence is a sequence only contains A, C, T and G, and it's very useful to analyze a segment of DNA Sequence,For example, if a animal's DNA sequence contains segment ATC then it may mean that the animal may have a genetic disease. Until now scientists have found several those segments, the problem is how many kinds of DNA sequences of a species don't contain those segments.

Suppose that DNA sequences of a species is a sequence that consist of A, C, T and G,and the length of sequences is a given integer n.

Input

First line contains two integer m (0 <= m <= 10), n (1 <= n <=2000000000). Here, m is the number of genetic disease segment, and n is the length of sequences.

Next m lines each line contain a DNA genetic disease segment, and length of these segments is not larger than 10.

Output

An integer, the number of DNA sequences, mod 100000.

Sample Input

4 3

AT

AC

AG

AA

Sample Output

36

[/toggle]

 

这俩题非常相似,给出文本串的长度和一些目标串,求所有经过/不经过单词节点的串的数量。

第一道题给的目标串数目多,而且比较长,所以在Trie树中节点数较多,而文本串长度较小,所以可以采用DP的思路搞出来:设f[i][j]:走了i步,当前在自动机上j号点时的方案总数。构建出trie图时,我们已经有了一个BFS顺序的栈,所以循环栈的下标即可按照广度优先的顺序递推出解。

第二道题则恰恰相反,Trie树中的节点数较少,但是文本串较长,递推不可做,所以我们考虑矩阵乘。对于邻接矩阵而言,对它进行自乘,得出的新矩阵中,s[i][j]即为i~j点的方案数。因此,构建一个邻接矩阵,设s[i][j]代表初始状态下自动机上的i点到j点的方案数,则通过Trie图的性质,枚举每个节点和它的子节点(包括虚拟的边),即可轻易实现。构建完成后,只需矩阵快速幂,最后统计root节点到每个点的方案数即可。

上代码:

[toggle hide="yes" title="BZOJ1030" color=""]

 

[/toggle]

[toggle hide="yes" title="POJ2778" color=""]

 

[/toggle]


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974