DNA Sequence
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.
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
思路是这样的:把所有病毒片段放入AC自动机中,建立fail数组。如果一个状态的fail为病毒节点,则他自己也为病毒节点。最后按边建矩阵,快速幂。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=;
const int mod=;
typedef unsigned long long ull;
struct Matrix{
int n;
ull mat[maxn][maxn];
Matrix(int n_,int on=){
n=n_;memset(mat,,sizeof(mat));
if(on)for(int i=;i<=n;i++)mat[i][i]=;
}
Matrix operator *(Matrix a){
Matrix ret(n);
unsigned long long l;
for(int i=;i<=n;i++)
for(int k=;k<=n;k++){
l=mat[i][k];
for(int j=;j<=n;j++)
(ret.mat[i][j]+=l*a.mat[k][j]%mod)%=mod;
}
return ret;
}
Matrix operator ^(long long k){
Matrix ret(n,);
while(k){
if(k&)
ret=ret**this;
k>>=;
*this=*this**this;
}
return ret;
}
}; struct AC_automation{
bool tag[maxn];
int cnt,rt,ch[maxn][],fail[maxn];
AC_automation(){
memset(tag,,sizeof(tag));
memset(fail,,sizeof(fail));
memset(ch,,sizeof(ch));cnt=rt=;
} int ID(char c){
if(c=='A')return ;
else if(c=='C')return ;
else if(c=='G')return ;
else return ;
} void Insert(char *s){
int len=strlen(s),p=rt;
for(int i=;i<len;i++)
if(ch[p][ID(s[i])])
p=ch[p][ID(s[i])];
else
p=ch[p][ID(s[i])]=++cnt;
tag[p]=true;
} void Build(){
queue<int>q;
for(int i=;i<;i++)
if(ch[rt][i])
fail[ch[rt][i]]=rt,q.push(ch[rt][i]);
else
ch[rt][i]=rt; while(!q.empty()){
int x=q.front();q.pop();
for(int i=;i<;i++)
if(ch[x][i]){
fail[ch[x][i]]=ch[fail[x]][i];
tag[ch[x][i]]|=tag[fail[ch[x][i]]];
q.push(ch[x][i]);
}
else
ch[x][i]=ch[fail[x]][i];
}
} void Solve(int k){
Matrix A(cnt);
for(int i=;i<=cnt;i++)
for(int j=;j<;j++)
if(!tag[i]&&!tag[ch[i][j]])
A.mat[ch[i][j]][i]+=;
A=A^k;
long long ans=;
for(int i=;i<=cnt;i++)
ans+=A.mat[i][];
printf("%lld\n",ans%mod);
}
}ac;
char s[maxn]; int main(){
#ifndef ONLINE_JUDGE
//freopen("","r",stdin);
//freopen("","w",stdout);
#endif
int tot,n;
scanf("%d%d",&tot,&n);
while(tot--){
scanf("%s",s);
ac.Insert(s);
}
ac.Build();
ac.Solve(n);
return ;
}