题面
题解
思想很重要： 最暴力的是p[i]表示AC自动机上每轮经过每个点的概率和（期望次数） 所有终止节点的概率之和=1。注意对于1号节点（AC自动机的根），概率要+1，因为一开始从它出发
然后我们发现对于所有非终止节点，我们统计每轮经过它们的概率和是没有任何意义的，我们可以把这些点放在一起考虑
所以就有了题解中的做法 只考虑在任一非终止节点后+串A，提前出现串B的概率
注意：概率高消eps越小越好？甚至设成0，然后系数选绝对值最大的优先，要不然精度会很爆炸
#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define per(i,a,b) for(int i=a;i>=b;--i) #define repd(i,a,b) for(int i=a;i>=b;--i) #define rvc(i,S) for(int i=0;i<(int)S.size();++i) #define fore(i,x) for(int i = head[x] ; i ; i = e[i].next) #define mp make_pair #define pb push_back #define fi first #define se second #define debug(...) fprintf(stderr,__VA_ARGS__) #define lowbit(x) (x&(-x)) using namespace std; #define maxn 1020 #define N 90020 #define eps 0 #define long double double double mat[maxn][maxn],f[maxn]; int n,T,l,a[maxn][maxn],s[maxn * 2],fail[maxn * 2];; char ch[maxn]; double pow2[maxn]; void getfail(int a[],int n){ fail[1] = 0; rep(i,2,n){ int p = fail[i - 1]; while ( p && a[i] != a[p + 1] ) p = fail[p]; fail[i] = a[i] == a[p + 1] ? p + 1 : 0; } } double kmp(int a[],int b[]){ int len = l * 2; rep(i,1,l) s[i] = a[i]; rep(i,1,l) s[i + l] = b[i]; getfail(s,len); double res = 0; int x = fail[len]; while ( x ){ res += pow2[l - x]; x = fail[x]; } /* while ( x ){ if ( fail[x] <= l && fail[x] ) res += pow2[l - fail[x]]; x = fail[x]; }*/ return res; } void build(){ pow2[0] = 1; rep(i,1,l) pow2[i] = pow2[i - 1] / 2; rep(i,1,n){ rep(j,1,n){ mat[i][j] = kmp(a[i],a[j]); // else mat[i][j] = 1; } mat[i][n + 1] = -pow2[l]; } rep(i,1,n + 2) mat[n + 1][i] = 1; mat[n + 1][n + 1] = 0; } void gauss(){ n++; /*rep(i,1,n){ rep(j,1,n + 1){ cout<<mat[i][j]<<" "; } cout<<endl; } */ rep(i,1,n){ int x = 0; rep(j,i,n){ if ( fabs(mat[j][i]) > eps ){ x = j; break; } } if ( fabs(mat[x][i]) < eps ) continue; if ( x != i ) rep(j,1,n + 1) swap(mat[x][j],mat[i][j]); rep(j,1,n){ if ( i != j && fabs(mat[j][i]) > eps ){ double tmp = mat[j][i] / mat[i][i]; rep(k,1,n + 1){ mat[j][k] -= tmp * mat[i][k]; } } } } /* rep(i,1,n){ rep(j,1,n + 1){ cout<<mat[i][j]<<" "; } cout<<endl; }*/ repd(i,n,1){ // if ( fabs(mat[i][i]) < eps ) continue; rep(j,i + 1,n) mat[i][n + 1] -= mat[i][j] * f[j]; f[i] = mat[i][n + 1] / mat[i][i]; } // rep(i,1,n) cout<<f[i]<<" "; // cout<<endl; } int main(){ // freopen("input.txt","r",stdin); scanf("%d %d",&n,&l); rep(i,1,n){ scanf("%s",ch + 1); rep(j,1,l){ if ( ch[j] == 'H' ) a[i][j] = 0; else a[i][j] = 1; } } build(); gauss(); rep(i,1,n - 1){ printf("%.10lf\n",(double)f[i]); } return 0; }