傳送門

題面：

背單詞，始終是復習英語的重要環節。在荒廢了3年大學生涯后，Lele也終于要開始背單詞了。?
一天，Lele在某本單詞書上看到了一個根據詞根來背單詞的方法。比如"ab",放在單詞前一般表示"相反，變壞，離去"等。?

于是Lele想，如果背了N個詞根，那這些詞根到底會不會在單詞里出現呢。更確切的描述是：長度不超過L，只由小寫字母組成的，至少包含一個詞根的單詞，一共可能有多少個呢？這里就不考慮單詞是否有實際意義。?

比如一共有2個詞根 aa 和 ab ，則可能存在104個長度不超過3的單詞，分別為?
(2個) aa,ab,?
(26個)aaa,aab,aac...aaz,?
(26個)aba,abb,abc...abz,?
(25個)baa,caa,daa...zaa,?
(25個)bab,cab,dab...zab。?

這個只是很小的情況。而對于其他復雜點的情況，Lele實在是數不出來了，現在就請你幫幫他。

Input

本題目包含多組數據，請處理到文件結束。?
每組數據占兩行。?
第一行有兩個正整數N和L。(0<N<6,0<L<2^31)?
第二行有N個詞根，每個詞根僅由小寫字母組成，長度不超過5。兩個詞根中間用一個空格分隔開。?

Output

對于每組數據，請在一行里輸出一共可能的單詞數目。?
由于結果可能非常巨大，你只需要輸出單詞總數模2^64的值。?

Sample Input

2 3 aa ab 1 2 a

Sample Output

104 52

題目分析：

? ? 又是一個AC自動機的好題。

? ? 本質上是bzoj1030和poj2778的綜合，只不過數據范圍更加大，更加麻煩一些。

? ? 首先如果數據范圍較小，我們直接可以用一個dp去求出不符合條件的方案數，用總方案數-不合法的方案數即為答案。

? ? 但是在這個題中數據范圍極大，因此我們必須用類似poj2778中的構造Trie圖跑矩陣快速冪的方法去做。

? ? 而因為題目中讓我們求的是至少包含1個模式串的方案數，因此我們需要求出（A為鄰接矩陣）。因此我們只需要在基礎的構建矩陣的過程中使矩陣多開一維，使得第i+1列全為1作為求和。

? ? 另外，因為要求至少包含一個模式串的方案數，因此在這種情況下，總方案數為：。顯然這個式子直接去快速冪去求必定也會超時，因此我們也得對這個式子進行矩陣優化，對于上述式子有：，設有，因此F(n)可轉化成矩陣形式：，此后再使用以此矩陣快速冪求解并讓求出的兩個結果相減即可。

? ? ps：因為題目中要求我們對2^64取模，因此我們只需要將所有變量開成unsigned long long即可（溢出時會自動對2^64取模）。

代碼：

#include <bits/stdc++.h> #define maxn 50 using namespace std; typedef unsigned long long ll; int n,m; char st[maxn]; struct Marix{//矩陣ll mo[maxn][maxn],n;Marix(){}Marix(int _n){n=_n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){mo[i][j]=0;}}} }; Marix mul(Marix a,Marix b){//矩陣相乘Marix res;res=Marix(a.n);for(int i=0;i<a.n;i++){for(int j=0;j<a.n;j++){for(int k=0;k<a.n;k++){res.mo[i][j]=res.mo[i][j]+a.mo[i][k]*b.mo[k][j];}}}return res; } Marix powMod(Marix a,ll n){//矩陣快速冪Marix res=Marix(a.n);for(int i=0;i<a.n;i++){res.mo[i][i]=1;}while(n){if(n&1) res=mul(res,a);a=mul(a,a);n>>=1;}return res; } struct Trie{//AC自動機int next[maxn][26],fail[maxn],End[maxn],root,id;int newnode(){for(int i=0;i<26;i++){next[id][i]=-1;}End[id]=0;return id++;}void init(){id=0;root=newnode();}void Insert(char *str){int len=strlen(str);int now=root;for(int i=0;i<len;i++){if(next[now][str[i]-'a']==-1){next[now][str[i]-'a']=newnode();}now=next[now][str[i]-'a'];}End[now]=1;}void build(){queue<int>que;for(int i=0;i<26;i++){if(next[root][i]==-1){next[root][i]=root;}else{fail[next[root][i]]=root;que.push(next[root][i]);}}while(!que.empty()){int now=que.front();que.pop();for(int i=0;i<26;i++){if(next[now][i]==-1){next[now][i]=next[fail[now]][i];}else{fail[next[now][i]]=next[fail[now]][i];que.push(next[now][i]);}}End[now]|=End[fail[now]];}}Marix get_Marix(){//構建矩陣Marix res=Marix(id+1);for(int i=0;i<id;i++){for(int j=0;j<26;j++){if(End[next[i][j]]) continue;res.mo[i][next[i][j]]++;}}for(int i=0;i<id+1;i++){//再多開一維，使得第id+1列全都置為1res.mo[i][id]=1;}return res;} }ac; int main() {while(~scanf("%d%d",&n,&m)){ac.init();for(int i=0;i<n;i++){scanf("%s",st);ac.Insert(st);}ac.build();Marix Mar1=ac.get_Marix();ll res=0;Mar1=powMod(Mar1,m);for(int i=0;i<Mar1.n;i++){res+=Mar1.mo[0][i];}res--;Marix Mar2=Marix(2);Mar2.mo[0][0]=26;Mar2.mo[1][1]=Mar2.mo[0][1]=1;Mar2=powMod(Mar2,m);ll ans=Mar2.mo[0][0]+Mar2.mo[0][1];ans--;ans-=res;printf("%I64u\n",ans);} }

?

轉載于:https://www.cnblogs.com/Chen-Jr/p/11007224.html

總結

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

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