题目链接：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在某本单词书上看到了一个根据词根来背单词的方法。比如"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。两个词根中间用一个空格分隔开。
每组数据占两行。
第一行有两个正整数N和L。(0<N<6,0<L<2^31)
第二行有N个词根，每个词根仅由小写字母组成，长度不超过5。两个词根中间用一个空格分隔开。
Output
对于每组数据，请在一行里输出一共可能的单词数目。
由于结果可能非常巨大，你只需要输出单词总数模2^64的值。
由于结果可能非常巨大，你只需要输出单词总数模2^64的值。
Sample Input
2 3
aa ab
1 2
a
aa ab
1 2
a
Sample Output
104
52
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 ;
}