題意：給出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+矩阵快速幂）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。