考研路茫茫——单词情结

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

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

题意：

给出m个单词，问长度不超过n且至少含有1个单词（可重叠）的字符串有多少个？

题解：

1.由于求“>=1”，那么可以先求出“<1”，即“=0”的有多少个，然后再用总的减去，得到答案。

2.“=0”，即不含有任何一个单词，详情请看：POJ2278 DNA Sequence 。

3. 由于长度<=n，那么我们要求 A^1 + A^2 + …… + A^n，其中A是初步得到的矩阵，怎么求？UVA11149 Power of Matrix 。

4. 最后用总的（26+26^2+……+26^n）减去不含单词的（A^1 + A^2 + …… + A^n 的初始状态那一行之和），即为答案。

代码如下：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <cmath>
  7 #include <queue>
  8 #include <stack>
  9 #include <map>
 10 #include <string>
 11 #include <set>
 12 using namespace std;
 13 typedef unsigned long long LL;
 14 const double EPS = 1e-6;
 15 const int INF = 2e9;
 16 const LL LNF = 9e18;
 17 const int MOD = 1e9+7;
 18 const int MAXN = 30+10;
 19 
 20 int Size;
 21 struct MA
 22 {
 23     LL mat[30][30];
 24     void init()
 25     {
 26         for(int i = 0; i<Size; i++)
 27         for(int j = 0; j<Size; j++)
 28             mat[i][j] = (i==j);
 29     }
 30 };
 31 
 32 MA operator+(const MA &x, const MA &y)
 33 {
 34     MA ret;
 35     memset(ret.mat, 0, sizeof(ret.mat));
 36     for(int i = 0; i<Size; i++)
 37     for(int j = 0; j<Size; j++)
 38         ret.mat[i][j] = x.mat[i][j]+y.mat[i][j];
 39     return ret;
 40 }
 41 
 42 MA operator*(const MA &x, const MA &y)
 43 {
 44     MA ret;
 45     memset(ret.mat, 0, sizeof(ret.mat));
 46     for(int i = 0; i<Size; i++)
 47     for(int j = 0; j<Size; j++)
 48     for(int k = 0; k<Size; k++)
 49         ret.mat[i][j] += 1LL*x.mat[i][k]*y.mat[k][j];
 50     return ret;
 51 }
 52 
 53 MA qpow(MA x, int y)
 54 {
 55     MA s;
 56     s.init();
 57     while(y)
 58     {
 59         if(y&1) s = s*x;
 60         x = x*x;
 61         y >>= 1;
 62     }
 63     return s;
 64 }
 65 
 66 MA solve(MA x, int n)
 67 {
 68     if(n==1) return x;
 69     MA s;
 70     s.init();
 71     s = (s+qpow(x,n/2))*solve(x, n/2);
 72     if(n%2) s = s+qpow(x, n);
 73     return s;
 74 }
 75 
 76 struct Trie
 77 {
 78     const static int sz = 26, base = 'a';
 79     int next[MAXN][sz], fail[MAXN], end[MAXN];
 80     int root, L;
 81     int newnode()
 82     {
 83         for(int i = 0; i<sz; i++)
 84             next[L][i] = -1;
 85         end[L++] = 0;
 86         return L-1;
 87     }
 88     void init()
 89     {
 90         L = 0;
 91         root = newnode();
 92     }
 93     void insert(char buf[])
 94     {
 95         int len = strlen(buf);
 96         int now = root;
 97         for(int i = 0; i<len; i++)
 98         {
 99             if(next[now][buf[i]-base] == -1) next[now][buf[i]-base] = newnode();
100             now = next[now][buf[i]-base];
101         }
102         end[now] = 1;
103     }
104     void build()
105     {
106         queue<int>Q;
107         fail[root] = root;
108         for(int i = 0; i<sz; i++)
109         {
110             if(next[root][i] == -1) next[root][i] = root;
111             else fail[next[root][i]] = root, Q.push(next[root][i]);
112         }
113         while(!Q.empty())
114         {
115             int now = Q.front();
116             Q.pop();
117             end[now] |= end[fail[now]];  //当前串的后缀是否也包含单词
118             for(int i = 0; i<sz; i++)
119             {
120                 if(next[now][i] == -1) next[now][i] = next[fail[now]][i];
121                 else fail[next[now][i]] = next[fail[now]][i], Q.push(next[now][i]);
122             }
123         }
124     }
125 
126     LL query(int n)
127     {
128         MA s;
129         memset(s.mat, 0, sizeof(s.mat));
130         for(int i = 0; i<L; i++)
131         {
132             if(end[i]) continue;  //存在单词的状态没有后继
133             for(int j = 0; j<sz; j++)
134                 if(end[next[i][j]]==0)   //存在单词的状态没有前驱
135                     s.mat[i][next[i][j]]++;  // i到next[i][j]的路径数+1。注意，当next[i][j]==root时，路径数很可能大于1。
136         }
137 
138         Size = L;
139         s = solve(s, n);
140         LL ret = 0;
141         for(int i = 0; i<L; i++)  //答案为：初始状态到各个状态（包括初始状态）的路径数之和。
142             ret += s.mat[0][i];
143         Size = 1;
144         memset(s.mat,0,sizeof(s.mat));  //26+26^2……+26^n。
145         s.mat[0][0] = 26;
146         s = solve(s, n);
147         return s.mat[0][0]-ret;
148     }
149 };
150 
151 Trie ac;
152 char buf[20];
153 int main()
154 {
155     int n, L;
156     while(scanf("%d%d", &n,&L)!=EOF)
157     {
158         ac.init();
159         for(int i = 1; i<=n; i++)
160         {
161             scanf("%s", buf);
162             ac.insert(buf);
163         }
164         ac.build();
165         LL ans = ac.query(L);
166         printf("%llu
", ans);
167     }
168     return 0;
169 }

View Code