又是AC自动机上用矩乘优化DP= =
其实和上一题基本一样。。。补集转化思想。。
只是要多弄一个小矩阵求(26^1+26^2+....+26^L)，并且也要求f的总和（因为是长度<=L）
直接调上一题的伪板子了= =
喜闻乐见CE了好几发。。。就因为iostream里有next这个名字的函数>_<（那我上一题怎么没CE啊摔
#include<cstdio>
#include<cstring>
#define ll long long
#define ull unsigned long long
using namespace std;
int dl[],fail[],num[];
int ch[][],tot,next[][];
ull mp[][];
ull c[][],tmp[][],ans;
int i,j,k,n,m,l,r,cnt;
bool gg[];
char s[]; ll tm[],t[]; inline void trie(int n){
int i,p=;
for(i=;i<n;i++){
s[i]-='a';
if(!ch[p][s[i]])ch[p][s[i]]=++tot,p=tot;
else p=ch[p][s[i]];
}
gg[p]=;//printf("gg: %d\n",p);
}
inline void getfail(){
int l=,r=,i,j,now,p;dl[]=;
while(l<r){
now=dl[++l];//printf(" %d fail:%d gg:%d\n",now,fail[now],gg[now]);
for(i=;i<;i++)if(ch[now][i]){
j=ch[now][i];//printf(" %d-->%d\n",now,j);
for(p=fail[now];p&&!ch[p][i];p=fail[p]);
if(!now)fail[j]=;else fail[j]=ch[p][i];
dl[++r]=j;gg[j]|=gg[fail[j]];
}
}
}
inline void getnext(){
l=,r=;int i,now,p;dl[]=;
while(l<r){
now=dl[++l];//printf(" %d\n",now);
for(i=;i<;i++){
if(ch[now][i]){
if(gg[ch[now][i]])next[now][i]=-;
else next[now][i]=ch[now][i],dl[++r]=ch[now][i];
}
else{
for(p=fail[now];p&&!ch[p][i];p=fail[p]);
next[now][i]=gg[ch[p][i]]?-:ch[p][i];
}
// printf("%d %d next:%d\n",now,i,next[now][i]);
}
}
}
inline void upd(){
cnt=;int i,j;
for(i=;i<=r;i++)
num[dl[i]]=++cnt;
for(i=;i<=r;i++){
j=dl[i];
for(k=;k<;k++)if(next[j][k]!=-)
mp[num[next[j][k]]][num[j]]++;
} // for(i=1;i<=r;puts(""),i++)
// for(j=1;j<=r;j++)printf(" %lld",mp[i][j]);
} inline void multoc(){
register int i,j,k;
for(i=;i<=cnt;i++)
for(j=;j<=cnt;j++)
for(tmp[i][j]=,k=;k<=cnt;k++)tmp[i][j]+=mp[i][k]*c[k][j];
for(i=;i<=cnt;i++)memcpy(c[i],tmp[i],(cnt+)<<);
}
inline void multomp(){
register int i,j,k;
for(i=;i<=cnt;i++)
for(j=;j<=cnt;j++)
for(tmp[i][j]=,k=;k<=cnt;k++)tmp[i][j]+=mp[i][k]*mp[k][j];
for(i=;i<=cnt;i++)memcpy(mp[i],tmp[i],(cnt+)<<);
} int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(i=;i<=n;i++)scanf("%s",s),trie(strlen(s));
getfail(),getnext(),upd();
cnt++;
for(i=;i<=cnt;i++)mp[cnt][i]=;
cnt++,mp[cnt][cnt]=,cnt++,mp[cnt][cnt-]=mp[cnt][cnt]=; // for(i=1;i<=cnt;puts(""),i++)for(j=1;j<=cnt;j++)printf(" %llu",mp[i][j]); for(i=;i<=cnt;i++)c[i][i]=; /* tm[1]=1;
for(i=1;i<=m;i++){
for(j=1;j<=cnt;j++)
for(k=1,t[j]=0;k<=cnt;k++)t[j]=(t[j]+mp[j][k]*tm[k])%modd;
memcpy(tm,t,sizeof(t));
}*/ while(m){
if(m&)
multoc();
m>>=;if(m)multomp();
// for(i=1;i<=cnt;puts(""),i++)for(j=1;j<=cnt;j++)printf(" %llu",c[i][j]);
} // for(i=1;i<=cnt;puts(""),i++)for(j=1;j<=cnt;j++)printf(" %llu",c[i][j]);
//for(i=1,ans=0;i<=cnt;i++)ans=(ans+c[i][1])%modd;
ull ans=c[cnt][cnt-]*;
for(i=;i<=cnt-;i++)ans-=c[i][];
printf("%I64u\n",ans+); memset(mp,,sizeof(mp)),memset(c,,sizeof(c)),
memset(ch,,(tot+)**),memset(next,,(tot+)**),memset(fail,,(tot+)<<),memset(gg,,tot+),tot=;
}
// for(i=1,ans=0;i<=cnt;i++)ans=(ans+tm[i])%modd;
// printf("%lld\n",ans);
return ;
}