fork(1) download
copy 
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<cstring>
  4. #include<vector>
  5. using namespace std;
  6.  
  7. typedef struct p
  8. {
  9.     double a[27][27];
  10. }matrix;
  11.  
  12.  
  13. matrix mat_mul(matrix m,matrix n)
  14. {
  15.  
  16.     int i,j,k;
  17.     matrix b;
  18.     for(i=0;i<=25;i++)
  19.     {
  20.         for(j=0;j<=25;j++)
  21.         {
  22.             b.a[i][j]=0;
  23.             for(k=0;k<=25;k++)
  24.                 b.a[i][j]+=m.a[i][k]*n.a[k][j];
  25.         }
  26.     }
  27.     return b;
  28.  
  29. }
  30.  
  31.  
  32.  
  33. matrix pow_mat(matrix p,int k)
  34. {
  35.     matrix ans;
  36.     for(int i=0;i<=25;i++)
  37.         for(int j=0;j<=25;j++)
  38.            ans.a[i][j]=double(i==j);
  39.  
  40.     while(k)
  41.     {
  42.         if(k%2==1)
  43.             ans=mat_mul(ans,p);
  44.         k/=2;
  45.         p=mat_mul(p,p);
  46.     }
  47.  
  48.   return ans;
  49.  
  50. }
  51.  
  52. int main()
  53. {
  54. int t,n,i,j,k;
  55. char s[4],m[4];
  56. bool hash_string[26*26*26+26*26+26+2];
  57. //freopen("input.txt","r",stdin);
  58. scanf("%d",&t);
  59. while(t--)
  60. {
  61.    matrix p;
  62.    memset(hash_string,0,sizeof(hash_string));
  63.    double ans=0;
  64.     scanf("%d %d\n",&n,&k);
  65.     scanf("%s",s);
  66.     for(i=0;i<=25;i++)
  67.     {
  68.         for(j=0;j<=25;j++)
  69.         {
  70.             scanf("%lf",&p.a[i][j]);
  71.             //printf("%.2f ",x);
  72.         }
  73.         //printf("\n");
  74.     }
  75.  
  76.    matrix z=pow_mat(p,k);
  77.    /*for(i=0;i<=25;i++)
  78.     {
  79.         for(j=0;j<=25;j++)
  80.         {
  81.             printf("%.2f ",z.a[i][j]);
  82.         }
  83.         printf("\n");
  84.     }*/
  85.  
  86.    for(i=0;i<n;i++)
  87.    {
  88.        scanf("%s",m);
  89.       double temp=1;
  90.       int val=0;
  91.       for(j=0;j<strlen(m);j++)
  92.         val+=(val*26)+(m[j]-'a');
  93.       if(!hash_string[val])
  94.       {
  95.        if(strlen(s)==strlen(m))
  96.        {
  97.        for(j=0;j<strlen(m);j++)
  98.          temp*=z.a[s[j]-'a'][m[j]-'a'];
  99.  
  100.        ans+=temp;
  101.        }
  102.        hash_string[val]=true;
  103.       }
  104.        //cout<<temp<<endl;
  105.  
  106.    }
  107.  
  108. printf("%.6lf\n",ans);
  109.  
  110.  
  111. }
  112.  
  113. return 0;
  114. }
Success #stdin #stdout 0s 3300KB
comments (?)
stdin
copy 
1
2 1
a
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0.5 0 0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.1 0.9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
ab
b
stdout
copy 
0.000000
https://ideone.com/pgtqzj
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!