题目链接：https://vjudge.net/problem/HDU-2243

考研路茫茫——单词情结

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 的初始状态那一行之和），即为答案。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef unsigned long long LL;

 const double EPS = 1e-;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = +;

 int Size;

 struct MA

 {

     LL mat[][];

     void init()

     {

         for(int i = ; i<Size; i++)

         for(int j = ; j<Size; j++)

             mat[i][j] = (i==j);

     }

 };

 MA operator+(const MA &x, const MA &y)

 {

     MA ret;

     memset(ret.mat, , sizeof(ret.mat));

     for(int i = ; i<Size; i++)

     for(int j = ; j<Size; j++)

         ret.mat[i][j] = x.mat[i][j]+y.mat[i][j];

     return ret;

 }

 MA operator*(const MA &x, const MA &y)

 {

     MA ret;

     memset(ret.mat, , sizeof(ret.mat));

     for(int i = ; i<Size; i++)

     for(int j = ; j<Size; j++)

     for(int k = ; k<Size; k++)

         ret.mat[i][j] += 1LL*x.mat[i][k]*y.mat[k][j];

     return ret;

 }

 MA qpow(MA x, int y)

 {

     MA s;

     s.init();

     while(y)

     {

         if(y&) s = s*x;

         x = x*x;

         y >>= ;

     }

     return s;

 }

 MA solve(MA x, int n)

 {

     if(n==) return x;

     MA s;

     s.init();

     s = (s+qpow(x,n/))*solve(x, n/);

     if(n%) s = s+qpow(x, n);

     return s;

 }

 struct Trie

 {

     const static int sz = , base = 'a';

     int next[MAXN][sz], fail[MAXN], end[MAXN];

     int root, L;

     int newnode()

     {

         for(int i = ; i<sz; i++)

             next[L][i] = -;

         end[L++] = ;

         return L-;

     }

     void init()

     {

         L = ;

         root = newnode();

     }

     void insert(char buf[])

     {

         int len = strlen(buf);

         int now = root;

         for(int i = ; i<len; i++)

         {

             if(next[now][buf[i]-base] == -) next[now][buf[i]-base] = newnode();

             now = next[now][buf[i]-base];

         }

         end[now] = ;

     }

     void build()

     {

         queue<int>Q;

         fail[root] = root;

         for(int i = ; i<sz; i++)

         {

             if(next[root][i] == -) next[root][i] = root;

             else fail[next[root][i]] = root, Q.push(next[root][i]);

         }

         while(!Q.empty())

         {

             int now = Q.front();

             Q.pop();

             end[now] |= end[fail[now]];  //当前串的后缀是否也包含单词

             for(int i = ; i<sz; i++)

             {

                 if(next[now][i] == -) next[now][i] = next[fail[now]][i];

                 else fail[next[now][i]] = next[fail[now]][i], Q.push(next[now][i]);

             }

         }

     }

     LL query(int n)

     {

         MA s;

         memset(s.mat, , sizeof(s.mat));

         for(int i = ; i<L; i++)

         {

             if(end[i]) continue;  //存在单词的状态没有后继

             for(int j = ; j<sz; j++)

                 if(end[next[i][j]]==)   //存在单词的状态没有前驱

                     s.mat[i][next[i][j]]++;  // i到next[i][j]的路径数+1。注意，当next[i][j]==root时，路径数很可能大于1。

         }

         Size = L;

         s = solve(s, n);

         LL ret = ;

         for(int i = ; i<L; i++)  //答案为：初始状态到各个状态（包括初始状态）的路径数之和。

             ret += s.mat[][i];

         Size = ;

         memset(s.mat,,sizeof(s.mat));  //26+26^2……+26^n。

         s.mat[][] = ;

         s = solve(s, n);

         return s.mat[][]-ret;

     }

 };

 Trie ac;

 char buf[];

 int main()

 {

     int n, L;

     while(scanf("%d%d", &n,&L)!=EOF)

     {

         ac.init();

         for(int i = ; i<=n; i++)

         {

             scanf("%s", buf);

             ac.insert(buf);

         }

         ac.build();

         LL ans = ac.query(L);

         printf("%llu\n", ans);

     }

     return ;

 }

巴特西

HDU2243 考研路茫茫——单词情结 ——AC自动机、矩阵优化

考研路茫茫——单词情结

最新文章

热门文章