题目链接
题解
话说在前，此题卡精度，最好开long double
先建(AC)自动机
求期望，逆着求，设(f[i][j])为长度为(i)的串，当前匹配AC自动机(j)节点，之后能产生伤害的期望值
枚举转移，如果转移到一个单词节点，因为产生伤害的单词间不能相连，就直接跳回根节点
矩乘优化一下即可
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
#include<iomanip>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 80,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
char s[6][20];
int n,L,A,len[6];
int ch[maxn][26],fail[maxn],val[maxn],cnt;
void ins(int p){
int u = 0,id;
for (int i = 1; i <= len[p]; i++){
id = s[p][i] - 'a';
u = ch[u][id] ? ch[u][id] : (ch[u][id] = ++cnt);
}
val[u] = true;
}
void dfs(int u,int f){
if (val[f]) val[u] = true;
for (int i = 0; i < A; i++)
if (ch[u][i]) dfs(ch[u][i],u);
}
void getf(){
queue<int> q;
for (int i = 0; i < A; i++) if (ch[0][i]) q.push(ch[0][i]);
int u,v;
while (!q.empty()){
u = q.front(); q.pop();
for (int i = 0; i < A; i++){
v = ch[u][i];
if (!v){
ch[u][i] = ch[fail[u]][i];
continue;
}
fail[v] = ch[fail[u]][i];
q.push(v);
}
}
}
struct Matrix{
long double s[maxn][maxn];
int n,m;
Matrix(){cls(s);n = m = 0;}
}C,F;
inline Matrix operator *(const Matrix& a,const Matrix b){
Matrix c;
if (a.m != b.n) return c;
c.n = a.n; c.m = b.m;
for (int i = 0; i < c.n; i++)
for (int j = 0; j < c.m; j++)
for (int k = 0; k < a.m; k++)
c.s[i][j] += a.s[i][k] * b.s[k][j];
return c;
}
inline Matrix qpow(Matrix a,int b){
Matrix re; re.n = re.m = a.n;
for (int i = 0; i < re.n; i++) re.s[i][i] = 1;
for (; b; b >>= 1,a = a * a)
if (b & 1) re = re * a;
return re;
}
int main(){
n = read(); L = read(); A = read();
REP(i,n){
scanf("%s",s[i] + 1),len[i] = strlen(s[i] + 1);
ins(i);
}
dfs(0,0);
getf();
C.n = C.m = cnt + 2; long double x = 1.0 / A;
for (int i = 0; i <= cnt; i++){
if (val[i]) continue;
for (int j = 0; j < A; j++){
if (val[ch[i][j]]){
C.s[i][cnt + 1] += x;
C.s[i][0] += x;
}
else {
C.s[i][ch[i][j]] += x;
}
}
}
C.s[cnt + 1][cnt + 1] = 1;
F.n = cnt + 2; F.m = 1;
F.s[cnt + 1][0] = 1;
Matrix Fn = qpow(C,L) * F;
long double ans = Fn.s[0][0];
cout << fixed <<setprecision(12) << ans<<endl;
return 0;
}