Description
周末同学们非常无聊，有人提议，咱们扔硬币玩吧，谁扔的硬币正面次数多谁胜利。大家纷纷觉得这个游戏非常符
合同学们的特色，但只是扔硬币实在是太单调了。同学们觉得要加强趣味性，所以要找一个同学扔很多很多次硬币
，其他同学记录下正反面情况。用H表示正面朝上，用T表示反面朝上，扔很多次硬币后，会得到一个硬币序列。比
如HTT表示第一次正面朝上，后两次反面朝上。但扔到什么时候停止呢？大家提议，选出n个同学，每个同学猜一个
长度为m的序列，当某一个同学猜的序列在硬币序列中出现时，就不再扔硬币了，并且这个同学胜利，为了保证只
有一个同学胜利，同学们猜的n个序列两两不同。很快，n个同学猜好序列，然后进入了紧张而又刺激的扔硬币环节
。你想知道，如果硬币正反面朝上的概率相同，每个同学胜利的概率是多少。
这题真是妙啊。
我们首先设第i个同学赢的概率是p[i], 再假设存在一个很长的串 S , 它没有和任何串匹配，并且记它出现的概率为p[n+1](虽然它很长但是生成它也是有概率的）。
那么我们现在就相当于给S后面接一些字符，判断它是否能匹配上某个串。 接着我们考虑， 假如当前想要匹配的串的某个前缀是另外一个待匹配串的后缀，由于S的最后几项是未知的，那么有可能先让另外一个串匹配走了。 举个网上最常见的例子，假如当前要匹配的串A是TTH，而另外有一个串B是HTT，那么从S后面直接接了一个TTH的概率就是1/（2^3)，然而这个概率不仅仅包括了TTH匹配了的情况，还包括了可能S的末尾是H，加TT把B已经匹配好了剩下一位任选匹配上的概率，还包括了可能S的末尾是HT，加T也把B匹配好了的剩下两位任选匹配上的概率，即 1/8 * p[n+1] =p[A] + 1/2 p[B] + 1/4 p[B] + ... 省略号为其他与A有冲突的串 。即我们可以得到 0=-1/8 * p[n+1] +p[A] + 1/2 p[B] + 1/4 p[B] + ... 的方程组。n+1个变量，现在已经有了n个方程，再因为必须有一个赢，所有有p[1]-p[n]的和为1，这样n+1个变量n+1个方程就可以求解了。
注意这题的0.5^x不要预处理，用math库的，反正我一直我调了一个小时。
下附AC代码。
// luogu-judger-enable-o2
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#define maxn 305
#define double long double
using namespace std;
const double eps=1e-8;
int n,m,len;
int fail[maxn+maxn];
double mypow[maxn];
char s[maxn][maxn];
char t[maxn+maxn];
double a[maxn][maxn];
void kmp()
{
int i=0,j=-1; fail[0]=-1;
while(i<=m+m)
{
// cerr<<"its "<<i<<endl;
if(j==-1 || t[i]==t[j])
i++,j++,fail[i]=j;
else
j=fail[j];
}
}
double myabs(double now)
{
return now>0.0 ? now : -now;
}
double gauss()
{
for(int i=1;i<=n;i++)
{
int row=i;
for(int j=i+1;j<=n;j++)
if(myabs(a[j][i])>myabs(a[row][i]))
row=j;
if(row!=i)
for(int j=1;j<=n+1;j++)
swap(a[i][j],a[row][j]);
for(int j=i+1;j<=n;j++)
{
double temp=a[j][i]/a[i][i];
for(int k=i;k<=n+1;k++)
a[j][k]-=temp*a[i][k];
}
}
for(int i=n;i>=1;i--)
{
double ans=a[i][n+1]/a[i][i];
a[i][n+1]=ans;
for(int j=i-1;j>=1;j--)
{
a[j][n+1]-=ans*a[j][i];
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
mypow[0]=1.0;
for(int i=1;i<=n;i++)
mypow[i]=0.5*mypow[i-1];
// cerr<<"+1"<<endl;
for(int i=1;i<=n;i++)
{
len=0;
for(int j=1;j<=m;j++) t[len++]=s[i][j]; t[len++]='$';
// a[i][i]=1.0;
a[i][n+1]=-pow(0.5,m);
for(int j=1;j<=n;j++)
// if(i!=j)
{
len=m+1;
for(int k=1;k<=m;k++) t[len++]=s[j][k];
// for(int k=0;k<len;k++)
// cout<<t[k]<<" ";
// cout<<endl;
kmp();
int temp=fail[len];
// for(int k=1;k<=len;k++)
// cout<<t[k];
// cout<<endl;
// for(int k=1;k<=len;k++)
// cout<<fail[k]<<endl;
while(temp>=1)
{
a[i][j]+=pow(0.5,m-temp);
temp=fail[temp];
}
}
}
// cerr<<"+1"<<endl;
for(int i=1;i<=n;i++)
a[n+1][i]=1.0;
a[n+1][n+2]=1.0;
n++;
gauss();
for(int i=1;i<=n-1;i++)
printf("%.10Lf\n",a[i][n+1]);
}