DNA Sequence
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 17160 | Accepted: 6616 |
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
Source
//2017-08-10
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define ll long long using namespace std; const int K = ;
const int N = ;
const int M = ;
const int MOD = ; struct Matrix{
ll a[M*M][M*M];
int r, c;
}mat, tmp; Matrix multi(Matrix x, Matrix y)//矩阵乘法
{
Matrix z;
memset(z.a, , sizeof(z.a));
z.r = x.r, z.c = y.c;
for(int i = ; i < x.r; i++){
for(int k = ; k < x.c; k++)//加速优化
{
if(x.a[i][k] == ) continue;
for(int j = ; j< y.c; j++)
z.a[i][j] = (z.a[i][j] + (x.a[i][k] * y.a[k][j]) % MOD) % MOD;
}
}
return z;
} void Matrix_pow(int n)//矩阵快速幂
{
Matrix tmp;
tmp.c = mat.c;
tmp.r = mat.r;
memset(tmp.a, , sizeof(tmp.a));
for(int i = ; i < tmp.c; i++)
tmp.a[i][i] = ;
while(n){
if(n & )
tmp = multi(tmp, mat);
mat = multi(mat, mat);
n >>= ;
}
int ans = ;
for(int i = ; i < tmp.c; i++)
ans = (ans + tmp.a[][i]) % MOD;
printf("%d\n", ans);
} struct AC_automation
{
//node nodes[N], *root, *superRoot, *cur;
int nex[M*M][], fail[M*M], match[M*M];
int root, CNT;
int newNode(){
for(int i = ; i < K; i++)
nex[CNT][i] = -;
match[CNT++] = ;
return CNT-;
}
int Hash(char ch)
{
if(ch == 'A')return ;
else if(ch == 'C')return ;
else if(ch == 'T')return ;
else if(ch == 'G')return ;
}
void init(){
CNT = ;
root = newNode();
}
void Insert(char s[]){//向字典树中插入一个字符串
int n = strlen(s);
int cur = root;
for(int i = ; i < n; i++){
int p = Hash(s[i]);
if(nex[cur][p] == -)
nex[cur][p] = newNode();
cur = nex[cur][p];
}
match[cur]++;
}
void build(){//构建自动机
queue<int> que;
fail[root] = root;
for(int i = ; i < K; i++){
if(nex[root][i] == -)
nex[root][i] = root;
else{
fail[nex[root][i]] = root;
que.push(nex[root][i]);
}
}
while(!que.empty()){
int cur = que.front();
if(match[fail[cur]])match[cur] = ;
que.pop();
for(int i = ; i < K; i++){
if(nex[cur][i] == -){
nex[cur][i] = nex[fail[cur]][i];
}else{
fail[nex[cur][i]] = nex[fail[cur]][i];
que.push(nex[cur][i]);
}
}
}
}
void to_marix(){
memset(mat.a, , sizeof(mat.a));
mat.r = mat.c = CNT;
for(int i = ; i < CNT; i++){
for(int j = ; j < ; j++)
if(!match[nex[i][j]])
mat.a[i][nex[i][j]]++;
}
// for(int i = 0; i < CNT; i++){
// for(int j = 0; j < CNT; j++)
// cout<<mat.a[i][j]<<" ";
// cout<<endl;
// }
}
}; char str[M];
AC_automation ac; int main()
{
int n, m;
while(scanf("%d%d", &m, &n)!=EOF)
{
ac.init();
for(int i = ; i < m; i++){
scanf("%s", str);
ac.Insert(str);
}
ac.build();
ac.to_marix();
Matrix_pow(n);
} return ;
}