题意：长度不超过L，只由小写字母组成的，至少包含一个词根的单词，一共可能有多少个。
解题关键：利用补集转化的思想，先求一个词根也不包含的单词个数，然后用总的减去即可。长度不超过L需要用矩阵维数增加一倍来处理前缀和。
这里还有第二种考虑思路，只增加一维，自己写一个三维矩阵验证一下即可，最后一列每一行代表每一行的前缀和。
方法1：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
typedef unsigned long long ll;
const int N=;
const int MAXN=;
struct mat{
ll m[][];
};
ll m,n;
struct Trie{
int Next[MAXN][N],Fail[MAXN],root,tot;
bool End[MAXN];
int newnode(){
for(int i=;i<N;i++) Next[tot][i]=-;
End[tot++]=false;
return tot-;
}
void init(){
tot=;
root=newnode();
}
void insert(char buf[]){
int len=strlen(buf),now=root,k;
for(int i=;i<len;i++){
k=buf[i]-'a';
if(Next[now][k]==-) Next[now][k]=newnode();
now=Next[now][k];
}
End[now]=true;
}
void build(){
queue<int>que;
Fail[root]=root;
for(int i=;i<N;i++){
if(Next[root][i]==-) Next[root][i]=root;
else{
Fail[Next[root][i]]=root;
que.push(Next[root][i]);
}
}
while(!que.empty()){
int now=que.front();
que.pop();
if(End[Fail[now]]) End[now]=true;
for(int i=;i<N;i++){
if(Next[now][i]==-) Next[now][i]=Next[Fail[now]][i];
else{
Fail[Next[now][i]]=Next[Fail[now]][i];
que.push(Next[now][i]);
}
}
}
}
mat get_mat(){
mat B={};
for(int i=;i<tot;i++){
if(End[i]) continue;
for(int j=;j<N;j++){
if(End[Next[i][j]]==false) B.m[i][Next[i][j]]++;//不能直接置1
}
}
for(int i=;i<tot;i++){
B.m[i+tot][i]=B.m[i+tot][i+tot]=;
}
return B;
}
}; mat mul(mat &A,mat &B,int len){
mat C={};
for(int i=;i<len;i++){
for(int j=;j<len;j++){
for(int k=;k<len;k++){
C.m[i][j]+=A.m[i][k]*B.m[k][j];
}
}
}
return C;
} mat pow(mat A,ll n,int len){
mat B={};
for(int i=;i<len;i++) B.m[i][i]=;
while(n){
if(n&) B=mul(B,A,len);
A=mul(A,A,len);
n>>=;
}
return B;
} Trie ac;
char buf[];
int main(){
while(scanf("%llu%llu",&m,&n)!=EOF){
ac.init();
for(int i=;i<m;i++){
scanf("%s",buf);
ac.insert(buf);
}
ac.build();
mat B=ac.get_mat();
B=pow(B,n+,*ac.tot);
mat C={},D={},E={};
for(int i=;i<ac.tot;i++) C.m[i][i]=;
D=mul(B,C,*ac.tot);
E.m[][]=,E.m[][]=,E.m[][]=E.m[][]=;
E=pow(E,n+,);
ll res1=,res2=E.m[][];
for(int i=;i<ac.tot;i++){
if(i==) D.m[ac.tot][i]-=;
res1+=D.m[ac.tot][i];
}
printf("%llu\n",res2--res1);
}
return ;
}
法2：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
typedef unsigned long long ll;
const int N=;
const int MAXN=;
struct mat{
ll m[][];
};
ll m,n;
struct Trie{
int Next[MAXN][N],Fail[MAXN],root,tot;
bool End[MAXN];
int newnode(){
for(int i=;i<N;i++) Next[tot][i]=-;
End[tot++]=false;
return tot-;
}
void init(){
tot=;
root=newnode();
}
void insert(char buf[]){
int len=strlen(buf),now=root,k;
for(int i=;i<len;i++){
k=buf[i]-'a';
if(Next[now][k]==-) Next[now][k]=newnode();
now=Next[now][k];
}
End[now]=true;
}
void build(){
queue<int>que;
Fail[root]=root;
for(int i=;i<N;i++){
if(Next[root][i]==-) Next[root][i]=root;
else{
Fail[Next[root][i]]=root;
que.push(Next[root][i]);
}
}
while(!que.empty()){
int now=que.front();
que.pop();
if(End[Fail[now]]) End[now]=true;
for(int i=;i<N;i++){
if(Next[now][i]==-) Next[now][i]=Next[Fail[now]][i];
else{
Fail[Next[now][i]]=Next[Fail[now]][i];
que.push(Next[now][i]);
}
}
}
}
mat get_mat(){
mat B={};
for(int i=;i<=tot;i++) B.m[i][tot]=;
for(int i=;i<tot;i++){
if(End[i]) continue;
for(int j=;j<N;j++){
if(End[Next[i][j]]==false) B.m[i][Next[i][j]]++;//不能直接置1
}
}
return B;
}
}; mat mul(mat &A,mat &B,int len){
mat C={};
for(int i=;i<len+;i++){
for(int j=;j<len+;j++){
for(int k=;k<len+;k++){
C.m[i][j]+=A.m[i][k]*B.m[k][j];
}
}
}
return C;
} mat pow(mat A,ll n,int len){
mat B={};
for(int i=;i<len;i++) B.m[i][i]=;
while(n){
if(n&) B=mul(B,A,len);
A=mul(A,A,len);
n>>=;
}
return B;
} Trie ac;
char buf[];
int main(){
while(scanf("%llu%llu",&m,&n)!=EOF){
ac.init();
for(int i=;i<m;i++){
scanf("%s",buf);
ac.insert(buf);
}
ac.build();
mat B=ac.get_mat(); ll res1,res2;
B=pow(B,n+,ac.tot);
res1=B.m[][ac.tot]-; mat E={};
E.m[][]=,E.m[][]=,E.m[][]=E.m[][]=;
E=pow(E,n+,);
res2=E.m[][]; printf("%llu\n",res2--res1);
}
return ;
}