考研路茫茫——單詞情結(jié)

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4843????Accepted Submission(s): 1527

Problem Description 背單詞，始終是復(fù)習(xí)英語的重要環(huán)節(jié)。在荒廢了3年大學(xué)生涯后，Lele也終于要開始背單詞了。
一天，Lele在某本單詞書上看到了一個根據(jù)詞根來背單詞的方法。比如"ab",放在單詞前一般表示"相反，變壞，離去"等。

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

比如一共有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。

這個只是很小的情況。而對于其他復(fù)雜點(diǎn)的情況，Lele實(shí)在是數(shù)不出來了，現(xiàn)在就請你幫幫他。 ?

?

Input 本題目包含多組數(shù)據(jù)，請?zhí)幚淼轿募Y(jié)束。
每組數(shù)據(jù)占兩行。
第一行有兩個正整數(shù)N和L。(0<N<6,0<L<2^31)
第二行有N個詞根，每個詞根僅由小寫字母組成，長度不超過5。兩個詞根中間用一個空格分隔開。 ?

?

Output 對于每組數(shù)據(jù)，請?jiān)谝恍欣镙敵鲆还部赡艿膯卧~數(shù)目。
由于結(jié)果可能非常巨大，你只需要輸出單詞總數(shù)模2^64的值。 ?

?

Sample Input 2?3 aa ab 1 2 a ?

?

Sample Output 104 52

?

?

/* hdu 2243 考研路茫茫——單詞情結(jié)(AC自動+矩陣)給你m個子串,求包含至少一個子串的長度不大于n的字符串的種類數(shù) 所有可能： 26+26^2 + .... + 26^n 而且前面也求過一個子串都不包含的情況。即把他們的關(guān)系轉(zhuǎn)換成矩陣mat 一個都不包含的情況： mat + mat^2 +..... + mat^n 對于求 次方和. mat+... mat^6 = mat+mat^2+mat^3 + mat^3*(mat+mat^2+mat^3) 于是求出兩個的值然后減去即可// 矩陣求a走m步到b的方案數(shù) + A + A^2 + A^3 + ... + A^k的結(jié)果(兩個矩陣的經(jīng)典應(yīng)用) hhh-2016-04-23 22:33:39 */ #include <iostream> #include <vector> #include <cstring> #include <string> #include <cstdio> #include <queue> #include <algorithm> #include <functional> #include <map> using namespace std; #define lson (i<<1) #define rson ((i<<1)|1) typedef unsigned long long ll; typedef unsigned int ul; const int maxn = 40010; int tot;struct Matrix {int len;ll ma[50][50];Matrix() {}Matrix(int L){len = L;} };Matrix mult(Matrix ta,Matrix tb) {Matrix tc;tc.len = ta.len;for(int i = 0; i < ta.len; i++){for(int j = 0; j < ta.len; j++){tc.ma[i][j] = 0;for(int k = 0; k < ta.len; k++){tc.ma[i][j] = tc.ma[i][j]+(ll)ta.ma[i][k]*tb.ma[k][j];}}}return tc; }Matrix pow_mat(Matrix a,ll n) {Matrix cnt;cnt.len = a.len;memset(cnt.ma,0,sizeof(cnt.ma));for(int i = 0 ; i < cnt.len; i++)cnt.ma[i][i] = 1;while(n){if(n&1) cnt = mult(cnt,a);a = mult(a,a);n >>= 1;}return cnt; }Matrix Add(Matrix ta,Matrix tb) {Matrix tc;tc.len = ta.len;for(int i = 0;i < tc.len;i++){for(int j = 0;j < tc.len;j++){tc.ma[i][j] = (ta.ma[i][j]+tb.ma[i][j]);}}return tc; }struct Tire {int nex[50][26],fail[50],ed[50];int root,L;int newnode(){for(int i = 0; i < 26; i++)nex[L][i] = -1;ed[L++] = 0;return L-1;}void ini(){L = 0,root = newnode();}void inser(char buf[]){int len = strlen(buf);int now = root;for(int i = 0; i < len; i++){int ta = buf[i]-'a';if(nex[now][ta] == -1)nex[now][ta] = newnode();now = nex[now][ta];}ed[now] ++;}void build(){queue<int >q;fail[root] = root;for(int i = 0; i < 26; i++)if(nex[root][i] == -1)nex[root][i] = root;else{fail[nex[root][i]] = root;q.push(nex[root][i]);}while(!q.empty()){int now = q.front();q.pop();if(ed[fail[now]])ed[now] = 1;for(int i = 0; i < 26; i++){if(nex[now][i] == -1)nex[now][i] = nex[fail[now]][i];else{fail[nex[now][i]] = nex[fail[now]][i];q.push(nex[now][i]);}}}}Matrix to_mat(){Matrix mat(L);memset(mat.ma,0,sizeof(mat.ma));for(int i = 0;i < L;i++){for(int j = 0;j < 26;j++){if(!ed[nex[i][j]])mat.ma[i][nex[i][j]] ++;}}return mat;} };Matrix mat;Matrix cal(int n) {if(n == 1)return mat;Matrix tp = cal(n/2);if(n & 1){Matrix t = pow_mat(mat,n/2+1);tp = Add(tp,mult(t,tp));tp = Add(tp,t);}else{Matrix t = pow_mat(mat,n/2);tp = Add(tp,mult(t,tp));}return tp; }ll pow_mod(ll a,int n) {ll cnt = 1;while(n){if(n&1) cnt = cnt*a;a = a*a;n >>= 1;}return cnt; }ll ca(int n) {if(n == 1)return 26;ll tp = ca(n/2);if(n & 1){ll t = pow_mod(26,n/2+1);tp = tp+t+tp*t;}else{ll t = pow_mod(26,n/2);tp = tp+t*tp;}return tp; }Tire ac; char buf[20]; int main() {int n,m;while(scanf("%d%d",&m,&n) != EOF){ac.ini();for(int i = 1; i <= m; i++){scanf("%s",buf);ac.inser(buf);}ac.build();mat = ac.to_mat();Matrix ans = cal(n);ll tans = ca(n);ll t = 0;for(int i = 0;i < ans.len;i++){t += ans.ma[0][i];}printf("%I64u\n",tans-t);}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/Przz/p/5449301.html

總結(jié)

以上是生活随笔為你收集整理的hdu 2243 考研路茫茫——单词情结(AC自动+矩阵)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。