题链：
http://www.lydsy.com/JudgeOnline/problem.php?id=1444
题解.1：
概率dp，矩阵乘法，快速幂。
对所有串建立AC自动机，
那么如果在trie树的节点上转移到一个打了标记的节点，就意味着该标记对应的人取得胜利。
(由于题中明确说明串长相同，串又互不相同，所以即表明着建立AC自动机后整个trie树中只有n个打了标记的节点，同时不会存在某些节点无法转移的问题。)
然后建立trie.size×trie.size大小的转移矩阵trans，每个位置trans(i,j)表示i节点转移到j节点的概率：
初始矩阵:
if(trie.tag[i]) trans(i,i)=1;
else trans(i,trie.ch[i][c])+=p[c](枚举接下来的字符c)
此时这个矩阵的每个位置(i,j)就表明，从i走一步到j的概率。
然后将矩阵自乘很多次，就可以得到每个位置表示(i,j)从i走很多很多次后到j的概率。
那么答案就是trans(1,i).(i为打了tag标记的节点)：表示从初始位置走了很多很多次后到了一个串结尾位置的概率。
由于数据小，同时矩阵转移了很多次，可以把矩阵里存的十分接近理论概率值的概率直接看成答案。
复杂度((nl)^3logP)（转移了P次矩阵，我定的是转移23336666233336666ll多次）
代码.1：
#include<bits/stdc++.h>#define MAXN 15using namespace std;int N,M,L;int pos[MAXN];double p[MAXN];struct Matrix{int r,c;double a[MAXN*MAXN][MAXN*MAXN];void Reset(int _r,int _c){r=_r; c=_c; memset(a,0,sizeof(a));}void Identity(){for(int i=1;i<=r;i++) a[i][i]=1;}Matrix operator * (const Matrix &rtm) const{Matrix now; now.Reset(r,rtm.c);for(int i=1;i<=now.r;i++)for(int j=1;j<=now.c;j++)for(int k=1;k<=c;k++)now.a[i][j]+=a[i][k]*rtm.a[k][j];return now;}Matrix operator ^ (long long b) const{Matrix now,base; base=*this;now.Reset(r,c); now.Identity();for(;b;base=base*base,b>>=1)if(b&1) now=now*base;return now;}};struct Trie{int size,p;int ch[MAXN*MAXN][MAXN],tag[MAXN*MAXN];Trie():size(1){}void Insert(char *S){static int cnt; p=1;for(int i=0;i<L;i++){int c=S[i]-‘A‘;if(!ch[p][c]) ch[p][c]=++size;p=ch[p][c];}tag[p]=1; pos[++cnt]=p;}}T;struct ACAM{int fail[MAXN*MAXN];void Build(){static queue<int>Q;Q.push(1); fail[1]=0;while(!Q.empty()){int u=Q.front(); Q.pop();T.tag[u]|=T.tag[fail[u]];for(int c=0;c<M;c++){int k=fail[u];if(!T.ch[u][c]){T.ch[u][c]=k?T.ch[k][c]:1;continue;}while(k&&!T.ch[k][c]) k=fail[k];fail[T.ch[u][c]]=k?T.ch[k][c]:1;Q.push(T.ch[u][c]);}}}}A;int main(){Matrix trans;static char S[MAXN];ios::sync_with_stdio(0);cin>>N>>L>>M;for(int i=0,a,b;i<M;i++)cin>>a>>b,p[i]=1.0*a/b;for(int i=1;i<=N;i++)cin>>S,T.Insert(S);A.Build();trans.Reset(T.size,T.size);for(int i=1;i<=T.size;i++){if(T.tag[i]) trans.a[i][i]=1;else for(int c=0;c<M;c++)trans.a[i][T.ch[i][c]]+=p[c];}trans=trans^23336666233336666ll;cout<<fixed<<setprecision(2);for(int i=1;i<=N;i++)cout<<trans.a[1][pos[i]]<<endl;return 0;}
题解.2：
期望dp，高斯消元
对所有串建立AC自动机，那么问题就转变为类似 BZOJ_3143_[Hnoi2013]游走 这种题目。
令dp[i]表示经过trie树上的i号节点的期望次数,pro[j][i]表示从j点转移到i点的概率。
那么就可以列出如下转移方程：
$$dp[i]=\sum_{j->i}{dp[j]*pro[j][i]}$$
特别的：
1.当j为trie树是被打了个tag标记的节点时，则不能转移给其他节点
2.当i为1号节点时，要多加一个数值1表示刚开始就期望经过了一次。
上述式子的转移存在环，需要高斯消元。
因为到达了有tag标记的节点就结束游戏不再转移，所以期望到达所有tag节点的次数为1
也就是说，每个tag节点的期望就等于到达该节点对应的人胜利的概率。
复杂度O((nl)³)
代码.2：
#include<bits/stdc++.h>#define MAXN 15using namespace std;const double eps=1e-8;int N,M,L,fail;int id[MAXN];double a[MAXN*MAXN][MAXN*MAXN],g[MAXN],dp[MAXN*MAXN];double *A[MAXN*MAXN];int dcmp(double x){if(fabs(x)<eps) return 0;return x>0?1:-1;}struct ACAM{int size;int ch[MAXN*MAXN][MAXN],tag[MAXN*MAXN],fail[MAXN*MAXN];ACAM():size(1){}void Insert(char *S){static int p,cnt; p=1; bool fg=0;for(int i=0;i<L;i++){int c=S[i]-‘A‘;if(!ch[p][c]) ch[p][c]=++size;p=ch[p][c];}tag[p]=1; id[++cnt]=p;}void Build(){static queue<int>Q;Q.push(1); fail[1]=0;while(!Q.empty()){int u=Q.front(); Q.pop();tag[u]|=tag[fail[u]];for(int c=0;c<M;c++){int k=fail[u];if(!ch[u][c]){ch[u][c]=k?ch[k][c]:1;continue;}while(k&&!ch[k][c]) k=fail[k];fail[ch[u][c]]=k?ch[k][c]:1;Q.push(ch[u][c]);}}}}DS;void buildequation(){for(int i=1;i<=DS.size;i++) if(!DS.tag[i])for(int c=0;c<M;c++)a[DS.ch[i][c]][i]+=g[c];for(int i=1;i<=DS.size;i++) a[i][i]+=-1;a[1][DS.size+1]+=-1;for(int i=1;i<=DS.size;i++) A[i]=a[i];}void Gausselimination(int pos,int i){if(pos==DS.size+1||i==DS.size+1) return;for(int j=pos;j<=DS.size;j++) if(dcmp(A[j][i])!=0){swap(A[j],A[pos]); break;}if(dcmp(A[pos][i])!=0)for(int j=pos+1;j<=DS.size;j++){double k=A[j][i]/A[pos][i];for(int l=i;l<=DS.size+1;l++)A[j][l]-=k*A[pos][l];}Gausselimination(pos+(dcmp(A[pos][i])!=0),i+1);if(dcmp(A[pos][i])!=0){for(int l=i+1;l<=DS.size;l++)dp[i]+=A[pos][l]*dp[l];dp[i]=A[pos][DS.size+1]-dp[i];dp[i]=dp[i]/A[pos][i];}}int main(){static char S[15];ios::sync_with_stdio(0);cin>>N>>L>>M;for(int i=0,P,Q;i<M;i++)cin>>P>>Q,g[i]=1.0*P/Q;for(int i=1;i<=N;i++)cin>>S,DS.Insert(S);DS.Build();buildequation();Gausselimination(1,1);cout<<fixed<<setprecision(2);for(int i=1;i<=N;i++)cout<<fabs(dp[id[i]])<<endl;return 0;}
●BZOJ 1444 [Jsoi2009]有趣的游戏
原文地址：https://www.cnblogs.com/zj75211/p/8543044.html