题目大意：给你$N$个长度相等且互不相同的模式串，现在有一个字符串生成器会不断生成字符，其中每个字符出现的概率是$p_{i}/q_{i}$，当生成器生成的字符串包含了某个模式串，则拥有该模式串的玩家胜利，然后游戏立即结束，求每个玩家获胜的概率 $N<=10$
首先建出$Trie$图
接着设$f[i]$表示匹配时停在i的概率，可得$f[ch{k}]+=f[i]*p_{k}/q_{k}$
由于$N$很小，可以构建$dp$转移的邻接矩阵，由于生成器生成的串是无限长的，相当于把矩阵乘了无限次幂
可以耍赖一点...把矩阵自乘很多次，反正是保留小数卡精度过
正确的做法呢，就是利用等比数列求极限的方法，即$1/(1-p)$，1在这里是单位矩阵，$p$是邻接矩阵
然后对$(1-p)$这个矩阵求逆即可
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NN 105
#define maxn 100000
#define ll long long
#define dd double
#define uint unsigned int
#define mod 1000000007
#define idx(X) (X-'A')
#define eps (1e-9)
using namespace std; int n,m;
int ed[NN];
int p[],q[],L,num; struct M{
dd f[NN][NN*];
friend M operator * (const M &a,const M &b){
M ret;memset(&ret,,sizeof(ret));
for(int i=;i<n;i++)
for(int j=;j<n;j++)
for(int k=;k<n;k++)
ret.f[i][j]+=a.f[i][k]*b.f[k][j];
return ret;
}
int Gauss()
{
int nn=n*;
for(int i=;i<n;i++)
f[i][i+n]=;
for(int i=;i<n;i++)
{
for(int j=i;j<n;j++)
if(fabs(f[j][i])>eps){
for(int k=;k<nn;k++)
swap(f[i][k],f[j][k]);
break;
}
if(fabs(f[i][i])<eps) return ;
dd r=1.0/f[i][i];
for(int j=i;j<nn;j++)
f[i][j]*=r;
for(int j=;j<n;j++)
if(j!=i){
r=f[j][i];
for(int k=i;k<nn;k++)
f[j][k]=f[j][k]-r*f[i][k];
}
}
for(int i=;i<n;i++)
for(int j=;j<n;j++)
f[i][j]=f[i][j+n];
return ;
}
}; struct AC{
int ch[NN][],fail[NN],tot,win[NN];
void Build_Trie(char *str,int len,int id)
{
int x=;
for(int i=;i<=len;i++){
if(!ch[x][idx(str[i])])
ch[x][idx(str[i])]=++tot;
x=ch[x][idx(str[i])];
}ed[id]=x;win[x]=;
}
void Build_Fail()
{
queue<int>q;
for(int i=;i<m;i++)
if(ch[][i]) q.push(ch[][i]);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=;i<m;i++)
{
if(ch[x][i]){
fail[ch[x][i]]=ch[fail[x]][i];
q.push(ch[x][i]);
}else{
ch[x][i]=ch[fail[x]][i];
}
}
}
}
void Build_Martix(M &S)
{
for(int x=;x<=tot;x++)
if(!win[x]){
for(int i=;i<m;i++)
S.f[ch[x][i]][x]+=1.0*p[i]/q[i];
}
for(int i=;i<n;i++)
for(int j=;j<n;j++)
if(i!=j) S.f[i][j]=-S.f[i][j];
else S.f[i][j]=1.0-S.f[i][j];
}
}ac;
M ans,ni; int main()
{
//freopen("t1.in","r",stdin);
scanf("%d%d%d",&num,&L,&m);
for(int i=;i<m;i++)
scanf("%d%d",&p[i],&q[i]);
char str[];
for(int i=;i<=num;i++){
scanf("%s",str+);
ac.Build_Trie(str,L,i);}
ac.Build_Fail();
n=ac.tot+;
ac.Build_Martix(ans);
ans.Gauss();
for(int i=;i<=num;i++)
printf("%.2lf\n",ans.f[ed[i]][]);
return ;
}