题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2553
看了题解才会……
首先，给定一个串，最好的划分方式是按禁忌串出现的右端点排序，遇到能填的就填上。在 AC 自动机上就是一旦能走到一个禁忌串的终止节点，就 ans++ 并走到根去。
考虑怎么把 ans++ 也体现在矩阵乘法里。而且还要期望……
只要在矩阵里填上概率，最后就能算出期望了。体现 ans++ 的话，就是在 “从当前节点到根” 的同时给 “从当前节点到 tot ” 的概率也加上 \( \frac{1}{alphabet} \) 即可。
最后就看一下乘了 len 次之后从根走到 tot 点的值即可。
听说要开 long double 。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define db long double
using namespace std;
const int N=,K=;
int n,m,alp,tot=,c[N][K],fl[N],q[N]; db p;
char ch[N]; bool en[N];
struct Mtr{
db a[N][N];
Mtr(){for(int i=;i<=tot;i++)for(int j=;j<=tot;j++)a[i][j]=;};
Mtr operator* (const Mtr &b)const
{
Mtr c;
for(int i=;i<=tot;i++)
for(int k=;k<=tot;k++)
for(int j=;j<=tot;j++)
c.a[i][j]+=a[i][k]*b.a[k][j];
return c;
}
}t,ans;
void get_fl()
{
int he=,tl=;
for(int j=;j<alp;j++)
if(c[][j])q[++tl]=c[][j],fl[c[][j]]=;
else c[][j]=;
while(he<tl)
{
int k=q[++he]; if(en[fl[k]])en[k]=;
for(int j=;j<alp;j++)
{
if(c[k][j])
{
int cr=fl[k];
while(cr&&!c[cr][j])cr=fl[cr];
if(c[cr][j])fl[c[k][j]]=c[cr][j];
else fl[c[k][j]]=;
q[++tl]=c[k][j];
}
else
{
int cr=fl[k];
while(cr&&!c[cr][j])cr=fl[cr];
if(c[cr][j])c[k][j]=c[cr][j];
else c[k][j]=;
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&alp); p=1.0/alp;
for(int i=;i<=n;i++)
{
scanf("%s",ch+);
int d=strlen(ch+), cr=;
for(int j=;j<=d;j++)
{
int w=ch[j]-'a';
if(!c[cr][w])c[cr][w]=++tot;
cr=c[cr][w];
}
en[cr]=;
}
get_fl(); tot++; t.a[tot][tot]=;
for(int i=;i<tot;i++)
for(int j=;j<alp;j++)
{
if(en[c[i][j]]){ t.a[i][]+=p; t.a[i][tot]+=p;}
else t.a[i][c[i][j]]+=p;
}
ans=t; m--;
while(m)
{
if(m&)ans=ans*t; t=t*t;m>>=;
}
printf("%.10Lf\n",ans.a[][tot]);
return ;
}