|
?
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
/**
poj 2778 AC自动机与矩阵连乘
题目大意：给定一些模式串，问可以构造出多少中长度为n且不含模式串中的任何一个作为子串的字符串
解题思路：构造自动机，写出状态转移的矩阵，进行矩阵快速幂，其n次幂就表示长度为n。然后mat[0][i]就表示从根节点到状态点i长度为n的字符串有多少种
*/
#include
#include
#include
#include
#include
using namespace std; const int MOD=100000; struct Matrix { int mat[110][110],n; Matrix() {} Matrix(int _n) { n=_n; for(int i=0; i
Q; for(int i=0; i<4; i++) { if(next[root][i]==-1) next[root][i]=root; else { fail[next[root][i]]=root; Q.push(next[root][i]); } } while(!Q.empty()) { int now=Q.front(); Q.pop(); if(end[fail[now]]==1) end[now]=1; for(int i=0; i<4; i++) { if(next[now][i]==-1) next[now][i]=next[fail[now]][i]; else { fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } } Matrix getMatrix() { Matrix res=Matrix(L); for(int i=0; i
>=1; } return ret; } int main() { int n,m; while(~scanf(%d%d,&n,&m)) { ac.init(); for(int i=0;i
|