POJ 2778 DNA Sequence （自动机DP+矩阵快速幂）

题意：给出m个致病DNA片段，求长为n且不含致病片段的DNA序列共有多少种。

数据范围：0 <= m <= 10，1 <= n <=2000000000

这题初看起来与上一题差不多，但一看数据范围就傻了……

分析：先建m个致病DNA片段的自动机，然后求出自动机中结点之间转移的路径数目，这样就可以得到一个有向图，所求问题就变为从根结点出发，到达任意一点，所走路径长度为n且路径不经过危险结点的路径数目。再抽象一下，就是求一个边长均为1的有向图中2点之间长为n的路径数目，这就不难想到矩阵了。设G为邻接矩阵，则G^k中第i行j列的元素表示从i到j长为k的路径数目。

View Code #include <stdio.h> #include <string.h> #include <queue> using namespace std; #define M 11 #define LEN 15 #define SIZE (M*LEN) #define mod 100000typedef __int64 LL;int next[M*LEN][4]; int fail[M*LEN]; bool isend[M*LEN]; int m,n,node; LL mat[M*LEN][M*LEN]; LL tmp[M*LEN][M*LEN]; LL ans[M*LEN][M*LEN]; void init() {node=1;memset(next[0],0,sizeof(next[0])); } void add(int cur,int k) {memset(next[node],0,sizeof(next[node]));isend[node]=0;next[cur][k]=node++; } int hash(char c) {switch(c){case 'A': return 0;case 'C': return 1;case 'T': return 2;case 'G': return 3;} } void insert(char *s) {int i,k,cur;for(i=cur=0;s[i];i++){k=hash(s[i]);if(!next[cur][k]) add(cur,k);cur=next[cur][k];}isend[cur]=1; } void build_ac() {queue<int>q;int cur,nxt,tmp;fail[0]=0;q.push(0);while(!q.empty()){cur=q.front(),q.pop();for(int k=0;k<4;k++){nxt=next[cur][k];if(nxt){if(cur==0) fail[nxt]=0;else{for(tmp=fail[cur];tmp && !next[tmp][k];tmp=next[tmp][k]);fail[nxt]=next[tmp][k];}if(isend[fail[nxt]]) isend[nxt]=1;q.push(nxt);}else{next[cur][k]=next[fail[cur]][k];}}} } void build_mat() {int cur,nxt,k;memset(mat,0,sizeof(mat));for(cur=0;cur<node;cur++){if(isend[cur]) continue;for(k=0;k<4;k++){nxt=next[cur][k];if(!isend[nxt]) mat[cur][nxt]++;}} } void mat_mul(LL a[][SIZE],LL b[][SIZE]) {for(int i=0;i<node;i++){for(int j=0;j<node;j++){tmp[i][j]=0;for(int k=0;k<node;k++){tmp[i][j]+=a[i][k]*b[k][j];}tmp[i][j]%=mod;}} } void mat_pow(int k) {memset(ans,0,sizeof(ans));for(int i=0;i<node;i++) ans[i][i]=1;while(k){if(k&1){mat_mul(ans,mat);memcpy(ans,tmp,sizeof(tmp));}k>>=1;mat_mul(mat,mat);memcpy(mat,tmp,sizeof(tmp));} } void solve() {build_ac();build_mat();mat_pow(n);LL ret=0;for(int i=0;i<node;i++) ret+=ans[0][i];printf("%I64d\n",ret%mod); } int main() {char s[LEN];while(~scanf("%d%d",&m,&n)){init();for(int i=0;i<m;i++){scanf("%s",s);insert(s);}solve();}return 0; }

 

转载于:https://www.cnblogs.com/algorithms/archive/2012/08/08/2628813.html

总结

以上是生活随笔为你收集整理的POJ 2778 DNA Sequence （自动机DP+矩阵快速幂）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。