题目大意：给定n个长度为l的模式串，现在要用前m个大写字母生成一个随机串，每个字符有自己的出现几率，第一次出现的字符串获胜，求最终每个字符串的获胜几率
建出AC自动机，，搞出转移矩阵
如果某个节点是模式串那么这个节点只向自己连一条概率为1的出边
然后把转移矩阵自乘50遍即可
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 120using namespace std;int n,l,m,limit;int pos[M];char s[M];double possibility[M];namespace Aho_Corasick_Automaton{struct Trie{Trie *son[10],*fail;int ed;}*root,mempool[M],*C=mempool;void Insert(Trie *&p,char *s,int pos){if(!p) p=++C;if(!*s){p->ed=pos;::pos[pos]=p-mempool;return;}Insert(p->son[*s-'A'],s+1,pos);}void Build_Tree(){static Trie *q[M];int i,r=0,h=0;for(i=0;i<m;i++)if(root->son[i])(q[++r]=root->son[i])->fail=root;elseroot->son[i]=root;while(r!=h){Trie *p=q[++h];for(i=0;i<m;i++)if(p->son[i])(q[++r]=p->son[i])->fail=p->fail->son[i];elsep->son[i]=p->fail->son[i];}}}class Matrix{private:double xx[M][M];public:Matrix(){memset(xx,0,sizeof xx);}Matrix(bool){int i;memset(xx,0,sizeof xx);for(i=0;i<=limit;i++)xx[i][i]=1;}double* operator [] (int x){return xx[x];}friend void operator *= (Matrix &x,Matrix y){int i,j,k;Matrix z;for(i=1;i<=limit;i++)for(j=1;j<=limit;j++)for(k=1;k<=limit;k++)z[i][j]+=x[i][k]*y[k][j];x=z;}}f;int main(){using namespace Aho_Corasick_Automaton;int i,x,p,q;cin>>n>>l>>m;for(i=0;i<m;i++){scanf("%d%d",&p,&q);possibility[i]=(double)p/q;}for(i=1;i<=n;i++){scanf("%s",s+1);Insert(root,s+1,i);}Build_Tree();limit=C-mempool;for(i=1;i<=limit;i++){if(mempool[i].ed)f[i][i]=1;elsefor(x=0;x<m;x++)f[i][mempool[i].son[x]-mempool]+=possibility[x];}for(i=1;i<=50;i++)f*=f;for(i=1;i<=n;i++)printf("%.2lf\n",f[1][pos[i]]);return 0;}
快乐时，想想我的影子，我会在云上为你喝彩
