考研路茫茫——单词情结
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在某本单词书上看到了一个根据词根来背单词的方法。比如"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
题意：
给定$n$个字符串，问长为$l$的串，有多少个里面含有给定的这些字符串之一。
思路：
之前poj2778 https://www.cnblogs.com/wyboooo/p/9899944.html这道题求得是不含有字符串的情况。
那么这道题其实可以转换为，所有的情况减去不含有这些字符串的情况。
建立AC自动机，然后根据标记建立矩阵,矩阵快速幂$l+1$的幂次。
因为长度是小于等于$l$的都行，所以做$l+1$，这里会超$int$
然后对矩阵
$$
\begin{matrix}
26 & 0 \\
1 & 1
\end {matrix}
$$做$l$次快速幂，结果的第二行第一列乘26就是总的个数。
#include<iostream>
#include<bits/stdc++.h>
#include<cstdio>
#include<cmath>
//#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
//#include<set>
//#include<climits>
//#include<map>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
#define pi 3.1415926535
#define inf 0x3f3f3f3f const int maxn = ;
struct Tree{
int fail;
int son[];
int ed;
}AC[maxn];
int tot = ; void init()
{
for(int i = ; i <= tot; i++){
AC[i].fail = ;
AC[i].ed = ;
memset(AC[i].son, , sizeof(AC[i].son));
}
tot = ;
} void build(string s)
{
int len = s.length();
int now = ;
for(int i = ; i < len; i++){
if(AC[now].son[s[i] - 'a'] == ){
AC[now].son[s[i] - 'a'] = ++tot;
}
now = AC[now].son[s[i] - 'a'];
}
AC[now].ed += ;
} void get_fail()
{
queue<int>que;
AC[].fail = ;
for(int i = ; i < ; i++){
if(AC[].son[i] != ){
AC[AC[].son[i]].fail = ;
que.push(AC[].son[i]);
}
}
while(!que.empty()){
int u = que.front();
que.pop();
if(AC[AC[u].fail].ed)AC[u].ed++;
for(int i = ; i < ; i++){
if(AC[u].son[i] != ){
AC[AC[u].son[i]].fail = AC[AC[u].fail].son[i];
que.push(AC[u].son[i]);
}
else{
AC[u].son[i] = AC[AC[u].fail].son[i];
}
}
}
} struct matrix{
ull m[maxn][maxn];
int n;
matrix(){}
matrix(int _n)
{
n = _n;
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
m[i][j] = ;
}
}
}
matrix operator *(const matrix &b)const{
matrix ret = matrix(n);
//memset(ret.m, 0x3f, sizeof(ret.m));
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
for(int k = ; k < n; k++){
ret.m[i][j] += m[i][k] * b.m[k][j];
}
}
}
return ret;
}
void debug()
{
for(int i = ; i < n; i++){
for(int j = ; j <n; j++){
printf("%llu ", m[i][j]);
}
cout<<endl;
}
}
}g; ull pow_m(ull a, int n)
{
ull ret = ;
ull tmp = a;
while(n){
if(n & )ret *= tmp;
tmp *= tmp;
n >> ;
}
return ret;
} matrix pow_M(matrix a, ull x)
{
//a.debug();
matrix ret = matrix(a.n);
for(int i = ; i < a.n; i++){
ret.m[i][i] = ;
}
matrix tmp = a;
while(x){
if(x & )ret = ret * tmp;
tmp = tmp * tmp;
//tmp.debug();
//ret.debug();cout<<endl;
x >>= ;
}
return ret;
} matrix get_matrix()
{
matrix ret = matrix(tot + );
for(int i = ; i < tot; i++){
if(AC[i].ed)continue;
for(int j = ; j < ; j++){
if(AC[AC[i].son[j]].ed == false){
ret.m[i][AC[i].son[j]]++;
}
}
}
for(int i = ; i < tot + ; i++){
ret.m[i][tot] = ;
}
return ret;
} int n;
ull l;
int main()
{
while(scanf("%d%I64u", &n, &l) != EOF){
init();
for(int i = ; i < n; i++){
string s;
cin>>s;
build(s);
}
//cout<<l<<endl;
get_fail();
g = get_matrix();
//g.debug();
g = pow_M(g, l + );
//g.debug();
ull res = ;
/*for(int i = 0; i < g.n; i++){
res += g.m[0][i];
}*/
res = g.m[][tot] - ;
matrix T = matrix();
//S.m[0][0] = 26;S.m[1][0] = 0;
T.m[][] = ;T.m[][] = ;
T.m[][] = ;T.m[][] = ;
T = pow_M(T, l);
printf("%I64u\n", T.m[][] * - res);
}
return ;
}