您的位置: 首页  >  IT文章  >  hdu2243 考研路茫茫——单词情结【AC自动机】【矩阵快速幂】 考研路茫茫——单词情结

hdu2243 考研路茫茫——单词情结【AC自动机】【矩阵快速幂】 考研路茫茫——单词情结

分类: IT文章 • 2022-07-14 23:22:45

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7136    Accepted Submission(s): 2502


Problem Description
背单词，始终是复习英语的重要环节。在荒废了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
 
Author
linle
 
Recommend
lcy

题意：

给定$n$个字符串，问长为$l$的串，有多少个里面含有给定的这些字符串之一。

思路：

之前poj2778  https://www.cnblogs.com/wyboooo/p/9899944.html这道题求得是不含有字符串的情况。

那么这道题其实可以转换为，所有的情况减去不含有这些字符串的情况。

建立AC自动机，然后根据标记建立矩阵,矩阵快速幂$l+1$的幂次。

因为长度是小于等于$l$的都行，所以做$l+1$，这里会超$int$

然后对矩阵

$$

egin{matrix}

26 & 0 \

1 & 1 

end {matrix}

$$做$l$次快速幂，结果的第二行第一列乘26就是总的个数。

  1 #include<iostream>
  2 #include<bits/stdc++.h>
  3 #include<cstdio>
  4 #include<cmath>
  5 //#include<cstdlib>
  6 #include<cstring>
  7 #include<algorithm>
  8 #include<queue>
  9 #include<vector>
 10 //#include<set>
 11 //#include<climits>
 12 //#include<map>
 13 using namespace std;
 14 typedef long long LL;
 15 typedef unsigned long long ull;
 16 #define pi 3.1415926535
 17 #define inf 0x3f3f3f3f
 18 
 19 const int maxn = 160;
 20 struct Tree{
 21     int fail;
 22     int son[26];
 23     int ed;
 24 }AC[maxn];
 25 int tot = 0;
 26 
 27 void init()
 28 {
 29     for(int i = 0; i <= tot; i++){
 30         AC[i].fail = 0;
 31         AC[i].ed = 0;
 32         memset(AC[i].son, 0, sizeof(AC[i].son));
 33     }
 34     tot = 0;
 35 }
 36 
 37 void build(string s)
 38 {
 39     int len = s.length();
 40     int now = 0;
 41     for(int i = 0; i < len; i++){
 42         if(AC[now].son[s[i] - 'a'] == 0){
 43             AC[now].son[s[i] - 'a'] = ++tot;
 44         }
 45         now = AC[now].son[s[i] - 'a'];
 46     }
 47     AC[now].ed += 1;
 48 }
 49 
 50 void get_fail()
 51 {
 52     queue<int>que;
 53     AC[0].fail = 0;
 54     for(int i = 0; i < 26; i++){
 55         if(AC[0].son[i] != 0){
 56             AC[AC[0].son[i]].fail = 0;
 57             que.push(AC[0].son[i]);
 58         }
 59     }
 60     while(!que.empty()){
 61         int u = que.front();
 62         que.pop();
 63         if(AC[AC[u].fail].ed)AC[u].ed++;
 64         for(int i = 0; i < 26; i++){
 65             if(AC[u].son[i] != 0){
 66                 AC[AC[u].son[i]].fail = AC[AC[u].fail].son[i];
 67                 que.push(AC[u].son[i]);
 68             }
 69             else{
 70                 AC[u].son[i] = AC[AC[u].fail].son[i];
 71             }
 72         }
 73     }
 74 }
 75 
 76 struct matrix{
 77     ull m[maxn][maxn];
 78     int n;
 79     matrix(){}
 80     matrix(int _n)
 81     {
 82         n = _n;
 83         for(int i = 0; i < n; i++){
 84             for(int j = 0; j < n; j++){
 85                 m[i][j] = 0;
 86             }
 87         }
 88     }
 89     matrix operator *(const matrix &b)const{
 90         matrix ret = matrix(n);
 91         //memset(ret.m, 0x3f, sizeof(ret.m));
 92         for(int i = 0; i < n; i++){
 93             for(int j = 0; j < n; j++){
 94                 for(int k = 0; k < n; k++){
 95                     ret.m[i][j] += m[i][k] * b.m[k][j];
 96                 }
 97             }
 98         }
 99         return ret;
100     }
101     void debug()
102     {
103         for(int i = 0; i < n; i++){
104             for(int j = 0; j <n; j++){
105                 printf("%llu ", m[i][j]);
106             }
107             cout<<endl;
108         }
109     }
110 }g;
111 
112 ull pow_m(ull a, int n)
113 {
114     ull ret = 1;
115     ull tmp = a;
116     while(n){
117         if(n & 1)ret *= tmp;
118         tmp *= tmp;
119         n >> 1;
120     }
121     return ret;
122 }
123 
124 matrix pow_M(matrix a, ull x)
125 {
126     //a.debug();
127     matrix ret = matrix(a.n);
128     for(int i = 0; i < a.n; i++){
129         ret.m[i][i] = 1;
130     }
131     matrix tmp = a;
132     while(x){
133         if(x & 1)ret = ret * tmp;
134         tmp = tmp * tmp;
135         //tmp.debug();
136         //ret.debug();cout<<endl;
137         x >>= 1;
138     }
139     return ret;
140 }
141 
142 matrix get_matrix()
143 {
144     matrix ret = matrix(tot + 1);
145     for(int i = 0; i < tot; i++){
146         if(AC[i].ed)continue;
147         for(int j = 0; j < 26; j++){
148             if(AC[AC[i].son[j]].ed == false){
149                 ret.m[i][AC[i].son[j]]++;
150             }
151         }
152     }
153     for(int i = 0; i < tot + 1; i++){
154         ret.m[i][tot] = 1;
155     }
156     return ret;
157 }
158 
159 int n;
160 ull l;
161 int main()
162 {
163     while(scanf("%d%I64u", &n, &l) != EOF){
164         init();
165         for(int i = 0; i < n; i++){
166             string s;
167             cin>>s;
168             build(s);
169         }
170         //cout<<l<<endl;
171         get_fail();
172         g = get_matrix();
173         //g.debug();
174         g = pow_M(g, l + 1);
175         //g.debug();
176         ull res = 0;
177         /*for(int i = 0; i < g.n; i++){
178             res += g.m[0][i];
179         }*/
180         res = g.m[0][tot] - 1;
181         matrix T = matrix(2);
182         //S.m[0][0] = 26;S.m[1][0] = 0;
183         T.m[0][0] = 26;T.m[0][1] = 0;
184         T.m[1][0] = 1;T.m[1][1] = 1;
185         T = pow_M(T, l);
186         printf("%I64u
", T.m[1][0] * 26 - res);
187     }
188     return 0;
189 }

相关推荐