对于每一个合法串，都有很多种方案，我们不妨把这些方案记为，f1，f2，f3……fx

p = （f1+f2+f3+……+fk）*（f1+f2+f3+……+fk）；

把他展开是不是很简单！！！但是我怎么就想不到！！！

展开之后 再来看，是两个 fi * fj 的和

这两个fi和fj的方案相同，那么 可以把他看成两个人，两个人分别走，并且他们序列相同的概率。

dp[i][j][k] 第i秒，第一个人走在j位置，第二个人走在k位置。

1 #include 
      
        2 const long long mod = 1e9+7; 3 const double ex = 1e-10; 4 #define inf 0x3f3f3f3f 5 using namespace std; 6 int ran[60]; 7 double p[60][60]; 8 double dp[35][60][60]; 9 int main()10 {11     int T;12     scanf("%d",&T);13     while (T--){14         int n,m;15         scanf("%d%d",&n,&m);16         for (int i = 1; i<=n; i++){17             for (int j = 1; j <=n; j++){18                 cin >> p[i][j];19             }20         }21         int z;22         scanf("%d",&z);23         for (int i = 1; i<=n;i++){24             scanf("%d",&ran[i]);25         }26         dp[1][1][1] = 1;27         for (int i = 2; i<=m ;i++){28             for (int j = 1; j <=n ;j++){29                 for (int k = 1; k <=n ;k++){30                     dp[i][j][k] = 0;31                     if (ran[j]!=ran[k]) continue;32                     for (int frj = 1; frj <=n ; frj++){33                         if (abs(ran[j] - ran[frj]) > 2) continue;34                         for (int frk = 1; frk <=n ; frk++){35                             dp[i][j][k] += dp[i-1][frj][frk]*p[frj][j]*p[frk][k];36                         }37                     }38                 }39             }40         }41         double ans = 0;42         for (int i = 1; i<=n; i++)43             for (int j =  1; j <=n; j++)44                 ans += dp[m][i][j];45         printf("%.18f\n",ans);46     }47     return 0;48 }