建出AC自动机，每个点向两个儿子连边，可以得到一张有向图。参照 [SDOI2012]走迷宫 可以得到一个\(Tarjan\)+高斯消元的\(O((nm)^3)\)的做法。（理论有\(60\)分啊但是第\(5.6\)个点WA了smg）
其实\(O((nm)^3)\)就是 [JSOI2009]有趣的游戏...只需建出AC自动机一遍高斯消元即可，比上面那个不知道好写到哪里去。。
\(40\)分的做法问题在于状态（变量）太多。考虑把类似的状态合并成一个。
假设现在一共有两个串\(TTH\)和\(HTT\)，两个串的终止节点分别记作\(A,B\)，没有经过终止节点的状态记作\(N\)。
\(N\)加上\(TTH\)一定会终止，但是在逐字符加上\(TTH\)时可能有其它情况：\(N\)的后缀与\(TT\)相连在\(B\)终止、\(N\)的后缀与\(T\)相连在\(B\)终止......总起来就是：$$NTTH=A+BH+BTH$$
其中\(BH\)就表示\(N\)在\(B\)处终止，但多出来\(H\)。
因为\(N\)中出现\(B\)的概率就是\(p(B)\)，再在后面加特定的\(k\)个字符，概率就是\(p(B)\times\frac{1}{2^k}\)。
所以有：$$p(N)\times\frac18=p(A)+p(B)\times\frac12+p(B)\times\frac14\0.125p(N)=p(A)+0.75p(B)$$
扩展到多个串，记\(pre_{i,k}\)表示\(s_i\)长度为\(k\)的前缀，\(suf_{i,k}\)表示\(s_i\)长度为\(k\)的后缀，那么$$p(N+s_i)=p(s_i)+\sum_{j=1}n\sum_{k=1}m[pre_{i,k}=suf_{j,k}]\frac{1}{2{m-k}}p(s_j)=\frac{1}{2m}p(N)$$
这样我们就可以得到\(n\)个方程了，但是有\(n+1\)个变量，剩下的一个方程就是\(\sum_{i=1}^np_i=1\)。就可以高斯消元了。
复杂度\(O(n^3+n^2m)\)。
求任意两个串之间所有公共前后缀，可以哈希或KMP或者AC自动机。
对\(fail\)什么的忘的差不多了...具体写一下，也都写一遍...
哈希：没什么好说的。。前后缀哈希就把字符串看成一个\(P\)进制数好了。（向\(Kelin\ dalao\)学一波orz）
AC自动机： AC自动机上每个点向能走到它的串连一条边。然后从\(s_b\)的终止节点不断跳\(fail\)，所有经过节点\(x\)上连出的边\(s_a\)，都表示\(s_a\)长\(len_x\)的前缀和\(s_b\)的后缀相同。
KMP：对每个\(a\)串求出\(fail\)数组，拿\(s_a\)在\(s_b\)上匹配，最后的\(j\)指针位置就是\(s_a\)最长的等于\(s_b\)后缀的前缀，然后\(j\)不断跳\(fail[j]\)并统计答案即可。
哈希：
//2280kb 192ms
#include <cmath>
#include <cstdio>
#include <algorithm>
typedef long long LL;
const int N=305,seed=131,LIM=(1<<30)-1;
int pw[N],pre[N][N],suf[N][N];
double pw2[N],A[N][N],Ans[N];
void Gauss(int n)
{
for(int j=0; j<n; ++j)
{
int mx=j;
for(int i=j+1; i<n; ++i) if(fabs(A[mx][j])<fabs(A[i][j])) mx=i;
if(mx!=j) for(int k=j; k<=n; ++k) std::swap(A[mx][k],A[j][k]);
for(int i=j+1; i<n; ++i)
if(A[i][j])//还是不要写>eps了= =
{
double t=A[i][j]/A[j][j];
for(int k=j; k<=n; ++k) A[i][k]-=t*A[j][k];
}
}
for(int i=n-1; ~i; --i)
{
for(int j=i+1; j<n; ++j) A[i][n]-=A[i][j]*Ans[j];
Ans[i]=A[i][n]/A[i][i];
}
}
int main()
{
static char s[N];
int n,m; scanf("%d%d",&n,&m);
pw[0]=1, pw2[0]=1;
for(int i=1; i<=m; ++i) pw[i]=pw[i-1]*seed&LIM, pw2[i]=pw2[i-1]*0.5;
for(int i=1; i<=n; ++i)
{
scanf("%s",s+1);
for(int j=1; j<=m; ++j) pre[i][j]=(pre[i][j-1]+s[j]*pw[j-1])&LIM;
for(int j=1; j<=m; ++j) suf[i][j]=(suf[i][j-1]*seed+s[m-j+1])&LIM;
}
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
for(int k=1; k<=m; ++k)//pre[i][m]==suf[i][m] -> 1
if(pre[i][k]==suf[j][k]) A[i][j]+=pw2[m-k];
for(int i=1; i<=n; ++i) A[0][i]=1, A[i][0]=-pw2[m];
A[0][n+1]=1, Gauss(n+1);
for(int i=1; i<=n; ++i) printf("%.10lf\n",Ans[i]);
return 0;
}
AC自动机：
//4460kb 192ms(常数大点...结果跑的和哈希差不多)
#include <cmath>
#include <cstdio>
#include <algorithm>
typedef long long LL;
const int N=305,M=N*N;
double pw2[N],A[N][N],Ans[N];
struct AC_Automaton
{
int tot,len[M],son[M][2],fail[M],q[M],H[M],Enum,nxt[M],to[M],ed[N];
char s[N];
inline void AE(int u,int v)
{
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
}
void Insert(int n,int id)
{
scanf("%s",s);
int x=0;
for(int i=0,c; i<n; ++i)
{
if(!son[x][c=s[i]=='H']) len[son[x][c]=++tot]=len[x]+1;
x=son[x][c], AE(x,id);
}
ed[id]=x;
}
void Build()
{
int h=0,t=0;
if(son[0][0]) q[t++]=son[0][0];//, fail[son[0][0]]=0;
if(son[0][1]) q[t++]=son[0][1];//, fail[son[0][1]]=0;
while(h<t)
{
int x=q[h++];
for(int i=0,v; i<2; ++i)
if((v=son[x][i])) fail[v]=son[fail[x]][i], q[t++]=v;
else son[x][i]=son[fail[x]][i];
}
}
void Calc(int id,int m)
{
for(int x=ed[id]; x; x=fail[x])
for(int i=H[x]; i; i=nxt[i])
A[to[i]][id]+=pw2[m-len[x]];
}
}ac;
void Gauss(int n)
{
for(int j=0; j<n; ++j)
{
int mx=j;
for(int i=j+1; i<n; ++i) if(fabs(A[mx][j])<fabs(A[i][j])) mx=i;
if(mx!=j) for(int k=j; k<=n; ++k) std::swap(A[mx][k],A[j][k]);
for(int i=j+1; i<n; ++i)
if(A[i][j])//还是不要写>eps了= =
{
double t=A[i][j]/A[j][j];
for(int k=j; k<=n; ++k) A[i][k]-=t*A[j][k];
}
}
for(int i=n-1; ~i; --i)
{
for(int j=i+1; j<n; ++j) A[i][n]-=A[i][j]*Ans[j];
Ans[i]=A[i][n]/A[i][i];
}
}
int main()
{
int n,m; scanf("%d%d",&n,&m);
pw2[0]=1;
for(int i=1; i<=m; ++i) pw2[i]=pw2[i-1]*0.5;
for(int i=1; i<=n; ++i) ac.Insert(m,i);
ac.Build();
for(int i=1; i<=n; ++i) ac.Calc(i,m);
for(int i=1; i<=n; ++i) A[0][i]=1, A[i][0]=-pw2[m];
A[0][n+1]=1, Gauss(n+1);
for(int i=1; i<=n; ++i) printf("%.10lf\n",Ans[i]);
return 0;
}
KMP：
//1644kb 668ms(常数比哈希大复杂度还是满的)
#include <cmath>
#include <cstdio>
#include <algorithm>
typedef long long LL;
const int N=305,M=N*N;
int fail[N];
char s[N][N];
double pw2[N],A[N][N],Ans[N];
void Gauss(int n)
{
for(int j=0; j<n; ++j)
{
int mx=j;
for(int i=j+1; i<n; ++i) if(fabs(A[mx][j])<fabs(A[i][j])) mx=i;
if(mx!=j) for(int k=j; k<=n; ++k) std::swap(A[mx][k],A[j][k]);
for(int i=j+1; i<n; ++i)
if(A[i][j])//还是不要写>eps了= =
{
double t=A[i][j]/A[j][j];
for(int k=j; k<=n; ++k) A[i][k]-=t*A[j][k];
}
}
for(int i=n-1; ~i; --i)
{
for(int j=i+1; j<n; ++j) A[i][n]-=A[i][j]*Ans[j];
Ans[i]=A[i][n]/A[i][i];
}
}
void GetFail(char *s,int m)
{
for(int i=2,j=0; i<=m; ++i)
{
while(j && s[i]!=s[j+1]) j=fail[j];
fail[i]=s[i]==s[j+1]?++j:0;
}
}
double Calc(char *s,char *p,int m)
{
int j=0;
for(int i=1; i<=m; ++i)
{
while(j && p[i]!=s[j+1]) j=fail[j];
if(p[i]==s[j+1]) ++j;
}
// if(a==b) j=fail[j];// -> 会多统计一次1
double res=0;
for(; j; j=fail[j]) res+=pw2[m-j];
return res;
}
int main()
{
int n,m; scanf("%d%d",&n,&m);
pw2[0]=1;
for(int i=1; i<=m; ++i) pw2[i]=pw2[i-1]*0.5;
for(int i=1; i<=n; ++i) scanf("%s",s[i]+1);
for(int i=1; i<=n; ++i)
{
GetFail(s[i],m);
for(int j=1; j<=n; ++j) A[i][j]=Calc(s[i],s[j],m);
}
for(int i=1; i<=n; ++i) A[0][i]=1, A[i][0]=-pw2[m];
A[0][n+1]=1, Gauss(n+1);
for(int i=1; i<=n; ++i) printf("%.10lf\n",Ans[i]);
return 0;
}
考试的时候写的很沙雕的40分：
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define eps 1e-10
typedef long long LL;
const int N=304*304;
struct AC_Automaton
{
int tot,son[N][2],ed[N],fail[N],q[N],ref[304];
char s[304];
//----- Build AC-Automaton -----
void Insert(int l,int id)
{
scanf("%s",s);
int x=0;
for(int i=0; i<l; ++i)
{
int c=s[i]=='H';
if(!son[x][c]) son[x][c]=++tot;
x=son[x][c];
}
ref[ed[x]=id]=x;
}
void Build()
{
int h=0,t=0;
if(son[0][0]) q[t++]=son[0][0];//, fail[son[0][0]]=0;
if(son[0][1]) q[t++]=son[0][1];//, fail[son[0][1]]=0;
while(h<t)
{
int x=q[h++];
for(int i=0,v; i<2; ++i)
if((v=son[x][i])) fail[v]=son[fail[x]][i], q[t++]=v;
else son[x][i]=son[fail[x]][i];
}
// for(int i=0; i<=tot; ++i) printf("i:%d son:%d %d\n",i,son[i][0],son[i][1]); puts("");
}
//----- Build Graph and Gauss -----
int cnt,out[N],dfn[N],low[N],bel[N],id[N],in[N];
double f[N],A[1005][1005];
std::vector<int> scc[N];
struct Graph
{
int Enum,H[N],nxt[N*3],to[N*3];
inline void AE(int u,int v)
{
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
}
}G,I;
inline void AE(int u,int v)
{//重边 自环...
++out[u], G.AE(u,v), I.AE(v,u);
}
void Tarjan(int x)
{
static int Index=0,top=0,sk[N];
static bool ins[N];
dfn[x]=low[x]=++Index, sk[++top]=x, ins[x]=1;
for(int i=G.H[x],v; i; i=G.nxt[i])
if(!dfn[v=G.to[i]]) Tarjan(v), low[x]=std::min(low[x],low[v]);
else if(ins[v]) low[x]=std::min(low[x],dfn[v]);
if(dfn[x]==low[x])
{
++cnt; int sz=0;
do{
int t=sk[top--]; id[t]=sz++;
scc[cnt].push_back(t), bel[t]=cnt, ins[t]=0;
}while(sk[top+1]!=x);
}
}
void Gauss(int n)
{
// printf("Gauss(%d)\n",n);
// for(int i=0; i<n; ++i,puts(""))
// for(int j=0; j<=n; ++j) printf("%.3lf ",A[i][j]);
for(int j=0; j<n; ++j)
{
int mx=j;
for(int i=j+1; i<n; ++i) if(fabs(A[i][j])>fabs(A[mx][j])) mx=i;
// if(fabs(A[mx][j])<eps) continue;
if(mx!=j) for(int k=0; k<=n; ++k) std::swap(A[mx][k],A[j][k]);
for(int i=j+1; i<n; ++i)
if(fabs(A[i][j])>eps)//fabs!!!
{
double t=A[i][j]/A[j][j];
for(int k=j; k<=n; ++k)
A[i][k]-=t*A[j][k];
}
}
for(int i=n-1; ~i; --i)
{
for(int j=i+1; j<n; ++j) A[i][n]-=A[i][j]*A[j][n];
A[i][n]/=A[i][i];
}
// for(int i=0; i<n; ++i,puts(""))
// for(int j=0; j<=n; ++j) printf("%.3lf ",A[i][j]);
}
//----- Solve -----
void Solve(int n)
{
for(int i=0; i<=tot; ++i)
if(!ed[i]) AE(i,son[i][0]), AE(i,son[i][1]);//don't AE(i,fail[i])...
for(int i=0; i<=tot; ++i)
if(!dfn[i]) Tarjan(i);
// printf("cnt:%d\n",cnt);
// for(int i=1; i<=cnt; ++i)
// {
// printf("scc[%d] = ",i);
// for(int j=0,l=scc[i].size(); j<l; ++j) printf("%d ",scc[i][j]);
// puts("");
// }// puts("");
for(int x=0; x<=tot; ++x)
for(int i=G.H[x]; i; i=G.nxt[i])
if(bel[x]!=bel[G.to[i]]) ++in[bel[G.to[i]]];
int h=0,t=0; q[t++]=bel[0], f[0]=1;
while(h<t)
{
int now=q[h++],l=scc[now].size();
// printf("\nnow:%d\n",now);
for(int j=0; j<l; ++j)
{
int x=scc[now][j];// printf("x:%d f:%.5lf\n",x,f[x]);
for(int i=0; i<=l; ++i) A[j][i]=0;
A[j][j]=1, A[j][l]=f[x];
for(int i=I.H[x],v; i; i=I.nxt[i])
if(bel[v=I.to[i]]==now) A[j][id[v]]-=0.5;//-=: 重边...
}
Gauss(l);// puts("");
for(int j=0; j<l; ++j)
{
int x=scc[now][j]; f[x]=A[j][l];
// printf("x:%d f:%.5lf\n",x,f[x]);
for(int i=G.H[x],v; i; i=G.nxt[i])
if(bel[v=G.to[i]]!=now)
{
f[v]+=0.5*f[x];
// printf("v:%d(%d) f[v]:%.5lf\n",v,bel[v],f[v]);
if(!--in[bel[v]]) q[t++]=bel[v];
}
}
}
// for(int i=0; i<=tot; ++i) printf("f[%d]=%.5lf\n",i,f[i]); puts("");
for(int i=1; i<=n; ++i) printf("%.10lf\n",f[ref[i]]);
}
}ac;
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
int n,m; scanf("%d%d",&n,&m);
for(int i=1; i<=n; ++i) ac.Insert(m,i);
ac.Build(), ac.Solve(n);
return 0;
}