问题分析
首先一个显然的做法就是建出AC自动机，然后高斯消元。但是这样的复杂度是(O(n^3m^3))的。
我们发现其实只需要求AC自动机上(n)个状态的概率，而其余的概率是没有用的。我们不妨设(i)赢的概率是(P_i)。同时，我们令(P_0)为没有任何一个人赢的概率。
然后我们考虑从(P_0)转移到(P_i)。如果我们直接在(P_0)后面加上串(i)是可以的。这样的概率是(frac{1}{2^m}P_0)。
但是这样有一个问题：
我们从(P_0)转移到(P_i)的过程中，可能先转移到了(P_j)。比如说，我们在(P_0)后加了(k(0 < k < m))位就到了(j)。这种情况下，串(i)长度为(k)的前缀就等于串(j)长度为(k)的后缀。此时就相当于在(P_j)后接一个长为(m-k)的串到(P_i)，而这样的概率是(frac{1}{2^{m-k}}P_j)。
可以借助下图加深理解：
所以我们可以得到(n)个方程
[P_i=frac{1}{2^m}P_0-sum_{j=1}^nsum_{k=1}^m[substr(i,1,k)=substr(j,m-k+1)]frac{1}{2^{m-k}}P_j
]
其中(substr(i,j,k))表示串(i)从(j)到(k)所构成的子串。
然后还有(sumlimits_{i=1}^nP_i=1)，这样我们就有(n+1)个未知数，(n+1)个方程。然后你就稳了。
参考程序
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 310;
int n, m, A[ Maxn ][ Maxn ], Fail[ Maxn ][ Maxn ];
long double Pow[ Maxn ], B[ Maxn ][ Maxn ];
int main() {
scanf( "%d%d", &n, &m );
for( int i = 1; i <= n; ++i ) {
char Ch[ Maxn ];
scanf( "%s", Ch + 1 );
for( int j = 1; j <= m; ++j )
A[ i ][ j ] = ( Ch[ j ] == 'T' ) ? 1 : 0;
}
for( int i = 1; i <= n; ++i ) {
Fail[ i ][ 1 ] = 0;
int t = 0;
for( int j = 1; j < m; ++j ) {
while( t && A[ i ][ t + 1 ] != A[ i ][ j + 1 ] ) t = Fail[ i ][ t ];
if( A[ i ][ t + 1 ] == A[ i ][ j + 1 ] ) ++t;
Fail[ i ][ j + 1 ] = t;
}
}
Pow[ 0 ] = 1;
for( int i = 1; i <= m; ++i )
Pow[ i ] = Pow[ i - 1 ] * 0.5L;
for( int i = 1; i <= n; ++i )
for( int j = 1; j <= n; ++j ) {
B[ i ][ j ] = 0ll;
int t = 0;
for( int k = 1; k <= m; ++k ) {
while( t && A[ i ][ t + 1 ] != A[ j ][ k ] ) t = Fail[ i ][ t ];
if( A[ i ][ t + 1 ] == A[ j ][ k ] ) ++t;
}
if( i == j ) t = Fail[ i ][ t ];//注意不要漏掉这句
while( t ) {
B[ i ][ j ] += Pow[ m - t ];
t = Fail[ i ][ t ];
}
}
for( int i = 1; i <= n; ++i ) {
B[ i ][ 0 ] = -Pow[ m ];
B[ i ][ i ] += 1ll;
}
for( int i = 1; i <= n; ++i ) B[ 0 ][ i ] = 1;
B[ 0 ][ n + 1 ] = 1;
for( int i = 0; i <= n; ++i ) {
if( B[ i ][ i ] == 0ll )
for( int j = i + 1; j <= n; ++j ) {
if( B[ j ][ i ] )
for( int k = 0; k <= n + 1; ++k )
swap( B[ i ][ k ], B[ j ][ k ] );
break;
}
long double t = B[ i ][ i ];
for( int j = 0; j <= n + 1; ++j ) B[ i ][ j ] /= t;
for( int j = 0; j <= n; ++j ) {
if( j == i ) continue;
long double T = B[ j ][ i ];
for( int k = 0; k <= n + 1; ++k )
B[ j ][ k ] -= B[ i ][ k ] * T;
}
}
for( int i = 1; i <= n; ++i )
printf( "%.10Lf
", B[ i ][ n + 1 ] );
return 0;
}