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实在是数不出来了，现在就请你帮帮他。
于是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
aa ab
1 2
a
Sample Output
104
52
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[][],s[];
//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[][];
};
mtr tmmmt;
mtr mul(mtr a,mtr b)
{
mtr c;
memset(c.an,,sizeof(c.an));
int i,j,k;
for(i = ;i<e;i++)
for(j = ;j<e;j++)
for(k = ;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,,sizeof(r.an));
for(i = ;i<e;i++)
r.an[i][i] = ;
while(t)
{
if(t%) r = mul(r,a);
a = mul(a,a);
t/=;
}
return r;
}
struct node
{
node* nextt[],*fail;
ll num;
node()
{
for(ll i = ;i<;i++)
nextt[i] = NULL;
fail = NULL;
num = e;
}
};
node* root;
void insert()
{
ll l = strlen(s),i;
node* k = root;
for(i = ;i<l;i++)
{
ll id = s[i]-'a';
if(k->nextt[id] == NULL)
{
k->nextt[id] = new node();
if(i != l-) e++;
}
k = k->nextt[id];
}
k->num = ;
}
void build()
{
queue<node*> q;
node* k = root;
for(ll i = ;i<;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 = ;i<;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 == ) continue;
for(ll i = ;i<;i++)
{
node* temp = k;
bool bl = ;
while(temp!=NULL)
{
ll b = ;
if(temp->nextt[i]!=NULL) b = temp->nextt[i]->num;
if(b == )
{
bl = ;
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 = ;
break;
}
temp = temp->fail;
}
if(bl) tmmmt.an[][a]++;
if(k->nextt[i]!=NULL) q.push(k->nextt[i]);
}
}
} int main()
{
int i,j,k;
while(cin>>N>>L)
{
e = ;
memset(tmmmt.an,,sizeof(tmmmt.an));
root = new node();
e++;
for(i = ;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[][] = ;
// 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][] = tmmmt.an[e][e] = ;
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+);
// 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-][]);
}
return ;
}
尼玛可算是过啦