Description：

$N$ 个给定的、长度为 $M$ 的模式串。逐位随机生成 $01$ 串，问每个模式串被首先生成的概率。

$1\leqslant N,M\leqslant 300$

Solution1：

和 $CTSC2006$ 歌唱王国类似，设 $F_k(x)$ 表示字符串在 $i$ 处以第 $k$ 个串结尾并且之前没有出现过其他模式串的串的个数的生成函数，那么我们要求的就是 $F_i(1/\Sigma)=F_i(0.5)$ 。

设 $G(x)$ 表示最后在第 $i$ 个位置出现了模式串，但是不一定是第一次出现的方案数的生成函数。 $$ G(x)=\sum_{i\geqslant 0}2^ix^i\times x^m $$ 含义就是前 $i$ 个可以是任意字符，最后 $m$ 个确定，那么有： $$ G=\frac{x^m}{1-2x} $$ 类似歌唱王国，设： $$ P_{a,b}=\sum_{i=1}^m[suf_a[i]=pre_b[i]]x^i $$ 最后一个串和之前不相交的结果是 $F_jG$ ，相交的结果是 $F_jP_{j,i}$ 那么就会有： $$ F_i=G-\sum_{j=1}^nF_j(G+P_{j,i}) $$

$$ \begin{align} F_i&=G-\sum_{j=1}^nF_j(G+P_{j,i})\\ F_i(x)&=\frac{x^m}{1-2x}-\sum_{j=1}^nF_j(x)(\frac{x^m}{1-2x}+P_{j,i}(x))\\ \end{align} $$

我们应该把 $x=0.5$ 代入，但是不能直接代入，因为分母是 $0$ ，所以我们先把分母乘上去然后再求导，据说这样再代入计算出的答案就是对的了，证明好像需要洛必达法则，不会： $$ \begin{align} (1-2x)F_i(x)&=x^m-\sum_{j=1}^nF_j(x)x^m-(1-2x)\sum_{j=1}^nF_j(x)P_{j,i}(x)\\ (1-2x)F'_i(x)-2F_i(x)&=mx^{m-1}-mx^{m-1}\sum_{j=1}^nF_j(x)-\sum_{j=1}^nx^mF_j'(x)+2\sum_{j=1}^nF_j(x)P_{j,i}(x)-(1-2x)\Bigl(\sum_{j=1}^nF_j(x)P_{j,i}(x)\Bigr)'\\ -2F_i(\frac12)&=m\frac1{2^{m-1}}-m\frac1{2^{m-1}}\sum_{j=1}^nF_j(\frac12)-\sum_{j=1}^n\frac1{2^m}F'_j(\frac12)+2\sum_{j=1}^nF_j(\frac12)P_{j,i}(\frac12)\\ F_i(\frac12)&=-m\frac1{2^m}+m\frac1{2^m}\sum_{j=1}^nF_j(\frac12)+\sum_{j=1}^n\frac1{2^{m+1}}F'_j(\frac12)-\sum_{j=1}^nF_j(\frac12)P_{j,i}(\frac12)\\ \end{align} $$ 于是设 $x_i=F_i(\frac12)$ ，那么我们就可以列出 $n$ 个方程，再加一个方程 $\sum x_i=1$ 就可以高斯消元了。

Solution2：

考虑直接套用歌唱王国那题的做法：

$F_i$ 表示第 $i$ 个序列成功的方案数， $G$ 表示未成功的方案数，那么依然有： $$ \sum_{i=1}^nF_i(x)+G(x)=xG(x)+1\\ G(x)(\frac 12x)^m=\sum_{j=1}^n\sum_{k=1}^ma_{i,j,k}F_j(x)(\frac 12x)^{m-k} $$ $a_{i,j,k}$ 表示第 $i$ 个序列的前 $k$ 位是否等于第 $j$ 个序列的后 $k$ 位。

然后还是对第一个式子求导： $$ \begin{align} \sum_{i=1}^nF'_i(x)+G'(x)&=xG'(x)+x'G(x)\\ \sum_{i=1}^nF'_i(1)&=G(1) \end{align} $$ 然后： $$ G(1)=\sum_{j=1}^n\sum_{k=1}^ma_{i,j,k}F_j(1)2^k $$ 于是我们可以列出 $n+1$ 个方程（最后一个是 $\sum F_i=1$ ）于是就可以高斯消元了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 310

int s[MAXN][MAXN];

#define BASE 19260817

#define MOD 1000000007

int power[MAXN];

double pow2[MAXN];

int getc()

{

	register char c = getchar();

	while(c != 'H' && c != 'T')c = getchar();

	return (c == 'H' ? 0 : 1);

}

struct hash

{

	int v[MAXN];

	int get(int l,int r)

	{

		return (v[r] - 1ll * v[l - 1] * power[r - l + 1] % MOD + MOD) % MOD;

	}

}h[MAXN];

int a[MAXN][MAXN][MAXN];

double g[MAXN][MAXN];

double b[MAXN];

double res[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	power[0] = 1;for(int i = 1;i <= m;++i)power[i] = 1ll * power[i - 1] * BASE % MOD;

	pow2[0] = 1;for(int i = 1;i <= m;++i)pow2[i] = pow2[i - 1] * 2;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			s[i][j] = getc();

			h[i].v[j] = (1ll * h[i].v[j - 1] * BASE % MOD + s[i][j]) % MOD;

		}

	}

	for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)for(int k = 1;k <= m;++k)

		a[i][j][k] = h[i].get(1,k) == h[j].get(m - k + 1,m);

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= n;++j)for(int k = 1;k <= m;++k)g[i][j] += a[i][j][k] * pow2[k];

		g[i][n + 1] = -1;

	}

	for(int i = 1;i <= n;++i)g[n + 1][i] = 1;

	b[n + 1] = 1;

	for(int i = 1;i <= n + 1;++i)

	{

		for(int j = i;j <= n + 1;++j)

		{

			if(fabs(g[i][j]) > 1e-8)

			{

				swap(g[i],g[j]);swap(b[i],b[j]);

				break;

			}

		}

		for(int j = i + 1;j <= n + 1;++j)

		{

			double delta = g[j][i] / g[i][i];

			for(int k = i;k <= n + 1;++k)

			{

				g[j][k] = g[j][k] - delta * g[i][k];

			}

			b[j] = b[j] - delta * b[i];

		}

	}

	for(int i = n + 1;i >= 1;--i)

	{

		res[i] = b[i] / g[i][i];

		for(int j = i - 1;j >= 1;--j)

		{

			b[j] -= g[j][i] * res[i];

		}

	}

	for(int i = 1;i <= n;++i)printf("%.10lf\n",res[i]);

	return 0;

}