一个直观的想法 是建AC自动机 然后消元 但是这样变量个数是 O(nm) 然后我就不会做了 概率题都好妙啊 一个精妙的设计是再定义一个状态N 表示当前串不包含任何人的概率 举个例子 来自这里
例如： A=TTH, B=HTT 那么N+TTH一定会到终止点，但不一定TTH加完后才停止 NTTH = A + BH + BTH 0.125N = A + 0.75B 获胜概率和为1 n+1个变量 n+1个方程 高斯消元
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } inline void read(char *s){ char c=nc(); int len=0; for (;!(c>='A' && c<='Z');c=nc()); for (;c>='A' && c<='Z';s[++len]=c,c=nc()); s[++len]=0; } const int N=305; int n,m; char s[N][N]; char S[N<<1]; int next[N<<1]; double pw[N]; inline double KMP(char *a,char *b){ for (int i=1;i<=m;i++) S[i]=a[i],S[m+i]=b[i]; int k=0; next[1]=0; for (int i=2;i<=(m<<1);i++){ while (k && S[k+1]!=S[i]) k=next[k]; if (S[k+1]==S[i]) k++; next[i]=k; } double ret=0; for (int t=m<<1;t;t=next[t]) if (t<=m) ret+=pw[m-t]; return ret; } double a[N][N]; inline void Gauss(int n){ for (int i=1;i<=n;i++){ int k=i; for (int j=i;j<=n;j++) if (fabs(a[j][i])>fabs(a[k][i])) k=j; if (k!=i) for (int j=1;j<=n+1;j++) swap(a[k][j],a[i][j]); for (int j=1;j<=n;j++){ if (i==j) continue; double t=a[j][i]/a[i][i]; for (int k=i;k<=n+1;k++) a[j][k]-=t*a[i][k]; } } } int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(n); read(m); for (int i=1;i<=n;i++) read(s[i]); pw[0]=1; for (int i=1;i<=m;i++) pw[i]=pw[i-1]/2.0; for(int i=1;i<=n;i++) a[n+1][i]=1; a[n+1][n+2]=1; for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++) a[i][j]=KMP(s[i],s[j]); a[i][n+1]=-pw[m]; } Gauss(n+1); for (int i=1;i<=n;i++) printf("%.10lf\n",a[i][n+2]/a[i][i]); return 0; }