注意 是0<=P, n , l, m≤ 10.

output 2
0.31
0.33
0.37

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 struct trnt{

     int ch[];

     int fl;

     bool fin;

 }tr[];

 class queue{

     public:

         queue(void){h=,t=;return ;}

         int nxt(int x){if(x+>=)return ;return x+;}

         void push(int x){t=nxt(t);line[t]=x;return ;}

         void pop(void){h=nxt(h);return ;}

         bool empty(void){return nxt(t)==h;}

         int front(void){return line[h];}

     private:

         int h,t,line[];

 }Q;

 int siz;

 int n,m,l;

 int ansp[];

 char tmp[];

 double lst[];

 double ans[];

 double martix[][];

 double temp[][];

 double pre[];

 void Insert(char *a,int &plc)

 {

     int root=;

     int len=l;

     for(int i=;i<=len;i++)

     {

         int c=a[i]-'A';

         if(!tr[root].ch[c])

             tr[root].ch[c]=++siz;

         root=tr[root].ch[c];

     }

     tr[root].fin=true;

     plc=root;

     return ;

 }

 void Build(void)

 {

     int root=;

     for(int i=;i<m;i++)

         if(tr[root].ch[i])

             Q.push(tr[root].ch[i]);

     while(!Q.empty())

     {

         root=Q.front();

         Q.pop();

         for(int i=;i<m;i++)

         {

             if(tr[root].ch[i])

             {

                 tr[tr[root].ch[i]].fl=tr[tr[root].fl].ch[i];

                 Q.push(tr[root].ch[i]);

             }else

                 tr[root].ch[i]=tr[tr[root].fl].ch[i];

         }

     }

     return ;

 }

 int main()

 {

     scanf("%d%d%d",&n,&l,&m);

     for(int i=;i<m;i++)

     {

         int a,b;

         scanf("%d%d",&a,&b);

         pre[i]=(double)(a)/(double)(b);

     }

     for(int i=;i<=n;i++)

     {

         scanf("%s",tmp+);

         Insert(tmp,ansp[i]);

     }

     Build();

     for(int i=;i<=siz;i++)

     {

         if(tr[i].fin)

         {

             martix[i][i]=1.00;

             continue;

         }

         for(int j=;j<m;j++)

             martix[i][tr[i].ch[j]]+=pre[j];

     }

     int t=;

     /*for(int i=0;i<=siz;i++)

     {

         for(int j=0;j<=siz;j++)

             printf("%.2lf ",martix[i][j]);

         puts("");

     }*/

     while(t--)

     {

         for(int i=;i<=siz;i++)

         {

             for(int j=;j<=siz;j++)

             {

                 temp[i][j]=;

                 for(int k=;k<=siz;k++)

                 {

                     temp[i][j]+=martix[i][k]*martix[k][j];

                 }

             }

         }

         for(int i=;i<=siz;i++)

             for(int j=;j<=siz;j++)

                 martix[i][j]=temp[i][j];

     }

     for(int i=;i<=n;i++)

         printf("%.2lf\n",martix[][ansp[i]]);

     return ;

 }