題目鏈接：https://vjudge.net/problem/POJ-2778

題意：輸入n和m表示n個病毒，和一個長為m的字符串，里面只可以有'A'，'C'，'G'，'T' 這四個字符，現在問這個長為m的字符串里面不可以出現任何病毒的情況有多少。

參考的兩篇博客：

http://www.cnblogs.com/LQLlulu/p/9344774.html

https://blog.csdn.net/morgan_xww/article/details/7834801

上面的博客寫得很好，可以主要看上面的博客（兩個一起看）。

寫點東西，不一定對。

因為最多10個病毒，每個病毒最多10個字符，所以我們trie樹上最多有100個點，其他空的點都指向根節點（也就是說我們把所有的空的節點看成0），這樣我們可以到達的點就只有100個（再重復一遍：我們把trie樹上面的空節點一律指向根節點，看成0），同時因為有些點是單詞的結尾或者他的fail[u]是單詞結尾（fail[u]是單詞結尾說明當前位置的后綴和fail[u]上的單詞相同，這個后綴也不能到達）。

我們一開始先構建一個cnt*cnt的鄰接矩陣mat（cnt是trie樹上面的節點個數），剛剛構建的mat[i][j]代表從編號為i的點走一步到達編號為j的點的合法（就是不經過單詞結尾或fail[u]是單詞結尾的點），在離散數學里面有一個結論，就是已知cnt個點之間兩兩互達（走一步）的可能數量（就是這個cnt*cnt的矩陣已經有了），那么如果我們要計算他們兩兩之間走n步到達的可能數量，只需要求出矩陣的n次方，這個矩陣的n次方就是點與點之間走n步到達的可能數量，這個可以聯想矩陣乘法的計算過程。

代碼：

#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<stack> #include<cmath> #include<vector> #include<set> #include<cstdio> #include<string> #include<deque> using namespace std; typedef long long LL; #define eps 1e-8 #define INF 0x3f3f3f3f #define maxn 105 int trie[maxn][4],fail[maxn],val[maxn]; LL mat[maxn][maxn],f[maxn][maxn],ss[maxn][maxn]; //mat[i][j]記錄從i到j有多少種可能，f[0][i]記錄以i結束的合法可能，其它維沒用，ss用來計算時暫時存儲 int n,m,k,t,cnt; char s[12]; void init(){memset(trie,0,sizeof(trie));memset(fail,0,sizeof(fail));memset(val,0,sizeof(val));memset(mat,0,sizeof(mat));memset(f,0,sizeof(f));f[0][0]=1; //一開始把根節點賦值為1,因為我們只需要第一行，所以可以只把f[0][0]賦值為1/*for(int i=0;i<maxn;i++)f[i][i]=1; */ //也可以這樣 cnt=0; } int getID(char a){if(a=='A')return 0;if(a=='T')return 1;if(a=='C')return 2;if(a=='G')return 3; } void insert(char *s){int root=0;for(int i=0;s[i];i++){int id=getID(s[i]);if(trie[root][id]==0)trie[root][id]=++cnt;root=trie[root][id];} val[root]=1;//標記單詞結尾 } void build_fail(){queue<int>q;int root=0;for(int i=0;i<4;i++){if(trie[root][i])q.push(trie[root][i]);}while(!q.empty()){int u=q.front();q.pop();if(val[fail[u]])//如果這個后綴是一個病毒，那么這個后綴也不可以到達 val[u]=1;for(int i=0;i<4;i++){if(trie[u][i]){fail[trie[u][i]]=trie[fail[u]][i];q.push(trie[u][i]);}else{trie[u][i]=trie[fail[u]][i];}}} } void build_mat(){//建圖 for(int i=0;i<=cnt;i++){for(int j=0;j<4;j++){if(val[trie[i][j]]==0&&val[i]==0)//當前狀態或接下來的的狀態是病毒都是不可以到達的 mat[i][trie[i][j]]++;}} } void muti(LL a[][maxn],LL b[][maxn]){//矩陣快速冪 memset(ss,0,sizeof(ss));for(int k=0;k<=cnt;k++)for(int i=0;i<=cnt;i++){for(int j=0;j<=cnt;j++){ss[i][j]+=a[i][k]*b[k][j];ss[i][j]%=100000;}}for(int i=0;i<=cnt;i++){for(int j=0;j<=cnt;j++){a[i][j]=ss[i][j];}} } int main() {while(scanf("%d%d",&n,&m)!=EOF){init();for(int i=0;i<n;i++){scanf("%s",s);insert(s);}build_fail();build_mat();//獲得走1步時的矩陣 while(m){if(m&1)muti(f,mat);muti(mat,mat);m>>=1;}LL ans=0;for(int i=0;i<=cnt;i++)ans=(ans+f[0][i])%100000;printf("%lld\n",ans);}return 0; }

?

轉載于:https://www.cnblogs.com/6262369sss/p/10304410.html

總結

以上是生活随笔為你收集整理的poj 2778 AC自动机+矩阵快速幂的全部內容，希望文章能夠幫你解決所遇到的問題。

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