Description
周末同学们非常无聊，有人提议，咱们扔硬币玩吧，谁扔的硬币正面次数多谁胜利。大家纷纷觉得这个游戏非常符
合同学们的特色，但只是扔硬币实在是太单调了。同学们觉得要加强趣味性，所以要找一个同学扔很多很多次硬币
，其他同学记录下正反面情况。用H表示正面朝上，用T表示反面朝上，扔很多次硬币后，会得到一个硬币序列。比
如HTT表示第一次正面朝上，后两次反面朝上。但扔到什么时候停止呢？大家提议，选出n个同学，每个同学猜一个
长度为m的序列，当某一个同学猜的序列在硬币序列中出现时，就不再扔硬币了，并且这个同学胜利，为了保证只
有一个同学胜利，同学们猜的n个序列两两不同。很快，n个同学猜好序列，然后进入了紧张而又刺激的扔硬币环节
。你想知道，如果硬币正反面朝上的概率相同，每个同学胜利的概率是多少。
Input
第一行两个整数n,m。
接下里n行，每行一个长度为m的字符串，表示第i个同学猜的序列。
1<=n,m<=300
Output
输出n行，第i行表示第i个同学胜利的概率。
输出与标准输出的绝对误差不超过10^-6即视为正确。
Sample Input
3 3 THT TTH HTT
Sample Output
0.3333333333 0.2500000000 0.4166666667
HINT
Source
数学问题 概率 高斯消元
kmp能想到，高斯消元能想到，然而不会列这个方程，沮丧
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int mxn=305; 8 int read(){ 9 int x=0,f=1;char ch=getchar();10 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}11 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}12 return x*f;13 }14 double f[mxn][mxn];15 double p[mxn];16 void Gauss(int n){17 int i,j;18 for(i=1;i<=n;i++){19 int p=i;20 for(j=i+1;j<=n;j++) if(fabs(f[j][i])>fabs(f[p][i]))p=j;21 if(p!=i)for(j=i;j<=n+1;j++)swap(f[i][j],f[p][j]);22 for(j=n+1;j>=i;j--) f[i][j]/=f[i][i];23 for(j=1;j<=n;j++){24 if(j==i)continue;25 double tmp=f[j][i];26 for(int k=1;k<=n+1;k++)27 f[j][k]-=f[i][k]*tmp;28 }29 }30 return;31 }32 int nxt[mxn];33 char s[mxn][mxn];34 int n,m;35 void getfail(int id){36 nxt[1]=0;37 for(int i=2,j=0;i<=m;i++){38 while(j && s[id][i]!=s[id][j+1])j=nxt[j];39 if(s[id][j+1]==s[id][i])j++;40 nxt[i]=j;41 }42 return;43 }44 void KMP(int id){45 for(int i=1;i<=n;i++){ //和所有串匹配 46 int j=0;47 for(int k=1;k<=m;k++){48 while(j && s[id][j+1]!=s[i][k])j=nxt[j];49 if(s[id][j+1]==s[i][k])j++;50 }51 for(;j;j=nxt[j])f[id][i]+=p[m-j];//,printf("%d to %d :%.5f\n",id,i,p[m-j]);52 }53 f[id][n+1]=-p[m];54 f[n+1][id]=1.0;55 return;56 }57 void Print(){58 for(int i=1;i<=n+1;i++){59 for(int j=1;j<=n+2;j++){60 printf("%.4lf ",f[i][j]);61 }62 puts("");63 }64 return;65 }66 int main(){67 int i,j;68 n=read();m=read();69 p[0]=1.0;70 for(i=1;i<=m;i++)p[i]=p[i-1]*0.5;71 for(i=1;i<=n;i++)scanf("%s",s[i]+1);72 for(i=1;i<=n;i++){73 getfail(i);74 KMP(i);75 }76 f[n+1][n+2]=1.0;77 // Print();78 Gauss(n+1);79 for(int i=1;i<=n;i++)80 printf("%.10f\n",f[i][n+2]);81 return 0;82 }83