诶这题洛谷居然没有？？？
题目链接: https://www.lydsy.com/JudgeOnline/problem.php?id=1444
题解: 我见到主要有三种做法。
一是矩阵乘法。设(dp[t][i])表示时间(t)之后在AC自动机(i)节点的概率，那么转移是一个矩阵乘法的形式，构造转移矩阵(f), 如果(u)是某个串的结尾点，则(f[u][u]=1,f[u][v]=0 (v e u)), 否则直接按概率搞。
然后这个矩阵的(t)次幂就可以得到(t)时刻后在每个点的概率。但是这题时间到无穷。
可以感觉到随着(t)的增加不匹配任何串的概率不断减小，(t)无穷大时达到0. 而题目精度要求并不高，所以如果我们能够使得(t)非常大而精度误差被控制在要求范围内，就做完了。
非常粗略地估算一下，(t=10^{12})时矩阵每一项的精度误差远小于(1 imes 10^{-4}) (别问我怎么算的，我放缩的幅度太大了，实际的界应该小于(10^{12}))
所以把矩阵自乘(40)次就完了。时间复杂度(O(n^6 imes 40)) (所有范围为(10)的参数不加以区分)
二是高斯消元。
对于任何节点(u), 其概率等于所有入边的概率乘上其字母权值之和，然后这样可以列出(siz) (AC自动机大小)个方程，但是如果这么解的话得到的答案是所有未知数全等于(0), 然后就把根的方程去掉，改成所有结束节点的概率之和等于(1), 解出来就A掉了……
完全不理解他是要干什么，拿某些题解代码一看，发现有的点解出来概率都是(2)……
到最后终于翻到一篇详细解释这个做法的题解: 如果设概率直接拿方程列上会全得(0), 原来这个未知数设的并非概率，而是经过该点的期望次数(对于结束节点期望次数就等于概率)，然后(x_0) ((0)为根)等于所有入边概率之和(+1) (因为上来先到一次), 其余节点等于所有入边概率之和即可解。也可以不要根的那个等式，换成所有结束节点期望次数之和为(1), 应该是等价的。(天哪看了一晚上终于看懂了……)
时间复杂度(O(n^6))
据说还有一个枚举每个人的(O(n^7))做法……大佬们太强了我啥都看不懂啊
三是矩阵求逆，这个貌似(对我来说)还好理解一些……
矩阵第(i)行第(j)列是从(i)转移到(j)的概率，结尾节点的这一行全部为0. 这个和做法一的区别就是结尾节点转移到自己的概率不是(1), 那么原来要求(T^{+inf})现在就变成要求(T+T^2+T^3+...+T^{+inf}), 这个矩阵元素都小于(1)应该收敛的，那么直接求(T imes (1-T)^{-1})即可。
时间复杂度(O(n^6))
代码
做法一
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int N = 10;
const int S = 10;
const int LEN = 10;
const int SIZ = 100;
const int LGM = 40;
int son[SIZ+3][S+3];
int fail[SIZ+3];
int que[SIZ+3];
double p[N+3];
int id[N+3];
char a[N+3][LEN+3];
int n,len,s,siz;
struct Matrix
{
double a[SIZ+3][SIZ+3];
Matrix operator *(const Matrix &arg) const
{
Matrix ret;
for(int i=0; i<=siz; i++) for(int j=0; j<=siz; j++) ret.a[i][j] = 0.0;
for(int i=0; i<=siz; i++)
{
for(int k=0; k<=siz; k++)
{
for(int j=0; j<=siz; j++)
{
ret.a[i][j] += a[i][k]*arg.a[k][j];
}
}
}
return ret;
}
} f;
void insertstr(char str[],int sid)
{
int u = 0;
for(int i=1; i<=len; i++)
{
if(son[u][str[i]]==0) {siz++; son[u][str[i]] = siz;}
u = son[u][str[i]];
}
id[sid] = u;
}
void buildACA()
{
int head = 1,tail = 0;
for(int i=1; i<=s; i++)
{
if(son[0][i]) {tail++; que[tail] = son[0][i];}
fail[son[0][i]] = 0;
}
while(head<=tail)
{
int u = que[head]; head++;
for(int i=1; i<=s; i++)
{
if(son[u][i]) {fail[son[u][i]] = son[fail[u]][i]; tail++; que[tail] = son[u][i];}
else {son[u][i] = son[fail[u]][i];}
}
}
}
int main()
{
scanf("%d%d%d",&n,&len,&s);
for(int i=1; i<=s; i++)
{
double x,y; scanf("%lf%lf",&x,&y); p[i] = x/y;
}
for(int i=1; i<=n; i++)
{
scanf("%s",a[i]+1); for(int j=1; j<=len; j++) a[i][j]-=64;
insertstr(a[i],i);
}
buildACA();
for(int u=0; u<=siz; u++)
{
for(int i=1; i<=s; i++)
{
int v = son[u][i];
f.a[u][v] += p[i];
}
}
for(int i=1; i<=n; i++)
{
int u = id[i];
for(int j=0; j<=siz; j++) f.a[u][j] = (u==j) ? 1.0 : 0.0;
}
for(int i=1; i<=LGM; i++)
{
f = f*f;
}
for(int i=1; i<=n; i++) printf("%.2lf
",f.a[0][id[i]]);
return 0;
}