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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<iomanip>
#define ll unsigned __int64
using namespace std;
ll N,L,e;
char ts[
10][
10],s[
10];
//int nextt[10],match[10];
//bool visit[10];
//bool kmp(char sa[],char sb[])
//{
// nextt[1] = 0;
// int i,j,k,l1 = strlen(sa+1),l2 = strlen(sb+1);
// for(i = 2;i<=l1;i++)
// {
// ll t = nextt[i-1];
// while(t&&sa[i]!=sa[t+1]) t = nextt[t];
// if(sa[i] == sa[t+1]) t++;
// nextt[i] = t;
// }
// match[0] = 0;
// for(i = 1;i<=l2;i++)
// {
// ll t = match[i-1];
// while(t&&sb[i]!=sa[t+1]) t = nextt[t];
// if(sb[i] == sa[t+1]) t++;
// match[i] = t;
// if(t == l1) return 1;
// }
// return 0;
//}
struct mtr
{
ll an[100][
100];
};
mtr tmmmt;
mtr mul(mtr a,mtr b)
{
mtr c;
memset(c.an,0,
sizeof(c.an));
int i,j,k;
for(i =
0;i<e;i++
)
for(j =
0;j<e;j++
)
for(k =
0;k<e;k++
)
c.an[i][j] += a.an[i][k]*
b.an[k][j];
return c;
}
mtr mpow(mtr a,ll t)
{
mtr r;
int i,j;
memset(r.an,0,
sizeof(r.an));
for(i =
0;i<e;i++
)
r.an[i][i] =
1;
while(t)
{
if(t%
2) r =
mul(r,a);
a =
mul(a,a);
t/=
2;
}
return r;
}
struct node
{
node* nextt[
26],*
fail;
ll num;
node()
{
for(ll i =
0;i<
26;i++
)
nextt[i] =
NULL;
fail =
NULL;
num =
e;
}
};
node*
root;
void insert()
{
ll l =
strlen(s),i;
node* k =
root;
for(i =
0;i<l;i++
)
{
ll id = s[i]-
'a';
if(k->nextt[id] ==
NULL)
{
k->nextt[id] =
new node();
if(i != l-
1) e++
;
}
k = k->
nextt[id];
}
k->num =
0;
}
void build()
{
queue<node*>
q;
node* k =
root;
for(ll i =
0;i<
26;i++
)
if(k->nextt[i]!=
NULL)
{
k->nextt[i]->fail =
k;
q.push(k->
nextt[i]);
}
while(!
q.empty())
{
node* k =
q.front();
q.pop();
for(ll i =
0;i<
26;i++
)
if(k->nextt[i] !=
NULL)
{
node* t = k->
fail;
while(t!=root&&t->nextt[i] == NULL) t = t->
fail;
if(t->nextt[i]!=NULL) t = t->
nextt[i];
k->nextt[i]->fail =
t;
q.push(k->
nextt[i]);
}
}
}
void ask()
{
queue<node*>
q;
q.push(root);
while(!
q.empty())
{
node* k =
q.front();
q.pop();
ll a = k->
num;
if(a ==
0)
continue;
for(ll i =
0;i<
26;i++
)
{
node* temp =
k;
bool bl =
1;
while(temp!=
NULL)
{
ll b =
1;
if(temp->nextt[i]!=NULL) b = temp->nextt[i]->
num;
if(b ==
0)
{
bl =
0;
tmmmt.an[b][a]++
;
break;
}
temp = temp->
fail;
}
if(!bl)
continue;
temp =
k;
while(temp!=
NULL)
{
if(temp->nextt[i]!=
NULL)
{
ll b = temp->nextt[i]->
num;
tmmmt.an[b][a]++
;
bl =
0;
break;
}
temp = temp->
fail;
}
if(bl) tmmmt.an[
1][a]++
;
if(k->nextt[i]!=NULL) q.push(k->
nextt[i]);
}
}
}
int main()
{
int i,j,k;
while(cin>>N>>
L)
{
e =
1;
memset(tmmmt.an,0,
sizeof(tmmmt.an));
root =
new node();
e++
;
for(i =
0;i<N;i++) scanf(
"%s",s),insert();
// for(i = 0;i<N;i++)
// {
// if(visit[i]) continue;
// for(j = 0;j<N;j++)
// {
// if(i == j) continue;
// if(kmp(ts[i],ts[j]))
// visit[j] = 1;
// }
// }
// for(i = 0;i<N;i++)
// {
// //if(visit[i]) continue;
// ll l = strlen(ts[i]+1);
// for(j = 0;j<=l;j++)
// s[j] = ts[i][j+1];
// insert();
// }
build();
ask();
tmmmt.an[0][
0] =
26;
// for(j = 0;j<e;j++)
// {
// ll sum = 0;
// for(i = 0;i<e;i++)
// {
// sum+=tmmmt.an[i][j];
// }
// tmmmt.an[1][j] = 26-sum;
// }
tmmmt.an[e][
0] = tmmmt.an[e][e] =
1;
e++
;
// for(i = 1;i<e-1;i++)
// {
// for(j = 1;j<e-1;j++)
// {
// cout<<setw(3)<<tmmmt.an[i][j];
// }
// cout<<endl;
// }
tmmmt = mpow(tmmmt,L+
1);
// for(i = 0;i<e;i++)
// {
// for(j = 0;j<e;j++)
// {
// cout<<tmmmt.an[i][j]<<" ";
// }
// cout<<endl;
// }
printf(
"%I64u\n",tmmmt.an[e-
1][
1]);
}
return 0;
}
尼玛可算是过啦
转载于:https://www.cnblogs.com/wos1239/p/4410493.html
