DNA Sequence
Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 14758 Accepted: 5716 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
AASample Output
36
【分析】
之前做过的题。 建立一个AC自动机，然后把每个字符串的最后一位所在的节点标黑。（就是把mark变为1） 然后用AC自动机建立矩阵array[i][j]表示从i走到j的方案数，然后利用矩阵乘法的性质，用快速幂求出矩阵的M次幂即可。 代码依然丑：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 1010
#define LL long long
#define Mod 100000 struct node
{
int x,fail;
int son[];
bool mark;
}t[Maxn];int tot=; struct Matrix
{
LL a[][];
}ay,ut; void upd(int x)
{
t[x].mark=;
memset(t[x].son,,sizeof(t[x].son));
} Matrix h;
void clear(int id)
{
for(int i=;i<=tot;i++)
for(int j=;j<=tot;j++)
if(id==) ay.a[i][j]=;
else h.a[i][j]=;
} int m,n;
char s[Maxn]; void read_trie()
{
scanf("%s",s+);
int len=strlen(s+);
int now=;
for(int i=;i<=len;i++)
{
int ind;
if(s[i]=='A') ind=;
else if(s[i]=='T') ind=;
else if(s[i]=='C') ind=;
else ind=;
if(!t[now].son[ind])
{
t[now].son[ind]=++tot,upd(tot);
}
now=t[now].son[ind];
if(i==len) t[now].mark=;
}
} queue<int > q;
void build_AC()
{
while(!q.empty()) q.pop();
q.push();
while(!q.empty())
{
int now=q.front();q.pop();
int f=t[now].fail;
for(int i=;i<=;i++)
{
if(t[now].son[i])
{
q.push(t[now].son[i]);
t[t[now].son[i]].fail=now?t[f].son[i]:;
if(t[t[t[now].son[i]].fail].mark) t[t[now].son[i]].mark=;
}
else t[now].son[i]=t[f].son[i];
if(t[t[now].son[i]].mark!=) ay.a[now][t[now].son[i]]++;
}
}
} Matrix mul(Matrix a,Matrix b)
{
clear();
for(int i=;i<=tot;i++)
for(int j=;j<=tot;j++)
for(int k=;k<=tot;k++)
{
h.a[i][j]=(h.a[i][j]+a.a[i][k]*b.a[k][j])%Mod; }
return h;
} void qpow(int k)
{
while(k)
{
if(k&) ut=mul(ut,ay);
ay=mul(ay,ay);
k>>=;
}
} void init()
{
scanf("%d%d",&m,&n);
tot=;upd();
for(int i=;i<=m;i++)
{
read_trie();
}
clear();
build_AC();
for(int i=;i<=tot;i++)
for(int j=;j<=tot;j++)
ut.a[i][j]=i==j?:; qpow(n);
LL ans=;
for(int i=;i<=tot;i++) ans=(ans+ut.a[][i])%Mod;
printf("%I64d\n",ans);
} int main()
{
init();
return ;
}
[POJ2778]
以前的code：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std; const int Maxn=;
const int Mod=(int)1e5;
char s[Maxn];
int q[Maxn];
long long ay[Maxn][Maxn],sum[Maxn][Maxn];
int n,m,tot,len; struct node
{
int son[],cnt,fail,mark;
}t[Maxn]; void floy()
{
tot=;
for(int i=;i<=Maxn;i++)
{
t[i].cnt=;t[i].mark=;
for(int j=;j<=;j++) t[i].son[j]=;
}
memset(q,,sizeof(q));
} void read_trie()
{
tot=;
int i,j;
scanf("%d%d",&m,&n);
for(i=;i<=m;i++)
{
int x,ind;
scanf("%s",s+);
len=strlen(s+);
x=;
for(j=;j<=len;j++)
{
if(s[j]=='A') ind=;
else if(s[j]=='C') ind=;
else if(s[j]=='T') ind=;
else if(s[j]=='G') ind=;
if(!t[x].son[ind]) t[x].son[ind]=++tot;
x=t[x].son[ind];
t[x].cnt++;
if(j==len) t[x].mark=;
}
}
} void build_AC()
{
int i,j,x,y;
q[++q[]]=;
//for(i=1;i<=4;i++)
//if(t[0].son[i]) q[++q[0]]=t[0].son[i];
for(i=;i<=q[];i++)
{
x=q[i];
y=t[x].fail;
for(j=;j<=;j++)
{
if(t[x].son[j])
{
//t[t[x].son[j]].fail=t[y].son[j];
q[++q[]]=t[x].son[j];
t[t[x].son[j]].fail=x?t[y].son[j]:x;
if(t[t[t[x].son[j]].fail].mark) t[t[x].son[j]].mark=;
}
else t[x].son[j]=t[y].son[j];
if(!t[t[x].son[j]].mark) ay[x][t[x].son[j]]++;
}
}
} void MatrixMult(long long a[Maxn][Maxn],long long b[Maxn][Maxn])
{
int i,j,k;
long long c[Maxn][Maxn];
memset(c,,sizeof(c));
for(i=;i<=tot;i++)
for(j=;j<=tot;j++)
for(k=;k<=tot;k++)
c[i][j]+=a[i][k]*b[k][j];
for(i=;i<=tot;i++)
for(j=;j<=tot;j++)
a[i][j]=c[i][j]%Mod;
} long long MatrixPow(int k)
{
int i,j;
for(i=;i<=tot;i++)
for(j=;j<=tot;j++)
sum[i][j]=(i==j);
while(k)
{
if(k&) MatrixMult(sum,ay);
MatrixMult(ay,ay);
k>>=;
}
long long ans=;
for(i=;i<=tot;i++) ans+=sum[][i];
return ans%Mod;
} int main()
{
floy();
read_trie();
build_AC();
printf("%I64d\n",MatrixPow(n));
return ;
}
[POJ2778_2]
2016-06-23 16:22:32