与POJ2778一样。这题是求长度不超过n且包含至少一个词根的单词总数。
长度不超过n的单词总数记为Sn，长度不超过n不包含词根的单词总数记为Tn。
答案就是，Sn-Tn。
Sn=26+262+263+...+26n
Tn=A+A2+A3+...+An （A为AC自动机构造出来的矩阵）
可以构造矩阵用快速幂求出Sn和Tn：
$$ \begin{bmatrix} 26 & 1 \\ 0 & 1 \end{bmatrix} \times \begin{bmatrix} S_n \\ 26 \end{bmatrix} = \begin{bmatrix} S_{n+1} \\ 26 \end{bmatrix}$$
$$ \begin{bmatrix} A & E \\ 0 & E \end{bmatrix} \times \begin{bmatrix} T_n \\ A \end{bmatrix} = \begin{bmatrix} T_{n+1} \\ A \end{bmatrix}$$
通过 $ \begin{bmatrix} 26 & 1 \\ 0 & 1 \end{bmatrix} ^n \times \begin{bmatrix} S_0 \\ 26 \end{bmatrix} = \begin{bmatrix} S_n \\ 26 \end{bmatrix}$ 即可得到Sn，其中S0=0，Tn同理。
另外题目结果mod 264这个直接把变量定义为unsigned __int64即可，溢出位数自动舍去。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int tn,ch[][],fail[];
bool flag[];
void insert(char *s){
int x=;
for(int i=; s[i]; ++i){
int y=s[i]-'a';
if(ch[x][y]==) ch[x][y]=++tn;
x=ch[x][y];
}
flag[x]=;
}
void init(int x){
memset(fail,,sizeof(fail));
queue<int> que;
for(int i=; i<; ++i){
if(ch[][i]) que.push(ch[][i]);
}
while(!que.empty()){
int x=que.front(); que.pop();
for(int i=; i<; ++i){
if(ch[x][i]) que.push(ch[x][i]),fail[ch[x][i]]=ch[fail[x]][i];
else ch[x][i]=ch[fail[x]][i];
flag[ch[x][i]]|=flag[ch[fail[x]][i]];
}
}
}
void init(){
memset(fail,,sizeof(fail));
queue<int> que;
for(int i=; i<; ++i){
if(ch[][i]) que.push(ch[][i]);
}
while(!que.empty()){
int now=que.front(); que.pop();
for(int i=; i<; ++i){
if(ch[now][i]) que.push(ch[now][i]),fail[ch[now][i]]=ch[fail[now]][i];
else ch[now][i]=ch[fail[now]][i];
flag[ch[now][i]]|=flag[ch[fail[now]][i]];
}
}
}
struct Mat{
unsigned long long m[][];
int n;
};
Mat operator*(const Mat &m1,const Mat &m2){
Mat m={};
m.n=m1.n;
for(int i=; i<m.n; ++i){
for(int j=; j<m.n; ++j){
for(int k=; k<m.n; ++k) m.m[i][j]+=m1.m[i][k]*m2.m[k][j];
}
}
return m;
}
int main(){
int n,l;
char str[];
while(~scanf("%d%d",&n,&l)){
tn=;
memset(ch,,sizeof(ch));
memset(flag,,sizeof(flag));
while(n--){
scanf("%s",str);
insert(str);
}
init();
Mat se={},sm={};
se.n=sm.n=;
for(int i=; i<; ++i) se.m[i][i]=;
sm.m[][]=; sm.m[][]=; sm.m[][]=;
n=l;
while(n){
if(n&) se=se*sm;
sm=sm*sm;
n>>=;
}
unsigned long long tot=se.m[][]*; Mat te={},tm={};
te.n=tm.n=tn+<<;
for(int i=; i<te.n; ++i) te.m[i][i]=;
for(int i=; i<=tn; ++i){
tm.m[i+tn+][i+tn+]=tm.m[i][i+tn+]=;
}
for(int i=; i<=tn; ++i){
if(flag[i]) continue;
for(int j=; j<; ++j){
if(flag[ch[i][j]]) continue;
++tm.m[i][ch[i][j]];
}
}
Mat tmp=tm; tmp.n=tn+;
n=l;
while(n){
if(n&) te=te*tm;
tm=tm*tm;
n>>=;
}
Mat tmp2; tmp2.n=tn+;
for(int i=; i<=tn; ++i){
for(int j=tn+; j<te.n; ++j) tmp2.m[i][j-tn-]=te.m[i][j];
}
tmp=tmp*tmp2;
unsigned long long res=;
for(int i=; i<=tn; ++i){
res+=tmp.m[][i];
}
printf("%llu\n",tot-res);
}
return ;
}