写在前面
此题网上存在大量题解，但本蒟蒻太菜了，看了不下10篇均未看懂，只好自己冷静分析了。本文将严格详细地论述算法（避免一切意会和玄学），因此可能会比其它题解更加理论化一些，希望能对像我一样看了其它题解还云里雾里的人有帮助。最后，为了追求极致，以下将字符串长度\(m\)加强到了10000（原题是300），并给出了一个时间复杂度到达极限的做法。
以下数学推导较多，如有错误之处欢迎批评指正！
题目描述
给定\(n\)个串，每个串仅包含字符T和F，长度均为\(m\)且互不相同。现在有一个字符串发生器，每次以等概率产生一个字符T或F，若某一时刻形成的字符串中出现了第\(i\)个串，则玩家\(i\)获胜。问每个玩家获胜的概率。
数据范围：\(n \le 300, m \le 10000\)
详细题解
一些定义
1、我们定义一个字符串\(T\)的\(q\)值为\(2^{-|T|}\)，可以理解为每个字母以\(1/2\)的概率生成（但并不是严格意义的概率）；
2、定义\(res(T)\)表示对于字符串\(T\)，哪个玩家获胜（当\(T\)的末尾匹配\(S_i\)，其它位置没有匹配任何给定串时，\(res(T)=i\)；若整个串都没有匹配任何给定串，\(res(T)=0\)；其他情况\(res(T)=-1\)）；
3、定义玩家\(i\)获胜的概率为\(P(i)\)；
4、定义字符串\(T_1\)和\(T_2\)的\(link\)为所有长度\(l\)的集合，使得\(T_1\)长为\(l\)的后缀与\(T_2\)长为\(l\)的前缀相同。
方程的建立
我们的最终目标是求出\(P(i)\)。下面我们建立关于未知数\(P(i)\)的方程组，并用高斯消元求解。
引理1：\(\displaystyle P(i)=\sum\limits_{res(T) = i} {q(T)} \)，且\(\displaystyle \sum\limits_{i = 1}^n {P(i)} = 1\)。
根据游戏规则可以得出。
引理2：对任意\(i\)，以下式子成立：
\[\sum\limits_{res(T) = 0} {q(T{S_i})} = \sum\limits_{j = 1}^n {P(j)\sum\limits_{l \in link({S_j},{S_i})} {{2^{l - m}}} } \]
证明：任取字符串\(T_j\)满足\(res(T_j)=j\)，以及\(l \in link({S_j},{S_i})\)，必然对应唯一一种方式，使得将\(T_j\)结尾添加\(m-l\)个字符后，长为\(m\)的后缀为\(S_i\)。若将\(T_j\)结尾添加\(m-l\)个字符后的字符串记做\(TS_i\)，则必有\(res(T) = 0\)。因此对等式右边每一个\(q(T_j)2^{l - m}\)必然对应且唯一对应等式左边一个\(q(TS_i)\)。另一方面，对于任意满足\(res(T) = 0\)的字符串\(TS_i\)，取它的最短的一个\(res\)不为0的前缀（记作\(T_j,res(T_j)=j\)），那么唯一对应了等式右边的\((T_j,l)\)对；而所有长度大于\(T_j\)长度的前缀必然\(res\)值都是-1，而所有小于\(T_j\)长度的前缀res值都为0，这就意味着等式左边\(q(TS_i)\)必然对应且唯一对应右边一个\(q(T_j)2^{l - m}\)。从而对应关系是一一对应，等式左边等于右边。证毕。
引理3：对任意\(i\)，\(\displaystyle \sum\limits_{res(T) = 0} {q(T{S_i})}\)的值均相同。
证明：对于每个\(i\)，该值均为\(\displaystyle \sum\limits_{res(T) = 0} {q(T)\times 2^{-m}}\)，故都相同。
根据引理2和引理3，我们便得到了\(n\)个关于\(P(i)\)的方程与一个附加未知数\(\displaystyle \sum\limits_{res(T) = 0} {q(T{S_i})}\)。再由引理1的第2式，便可列\(n+1\)个方程解\(n+1\)个未知数了。
\(link\)的计算
现在只剩一个问题，对任意\(i,j\)计算\(\displaystyle \sum\limits_{l \in link({S_j},{S_i})} {{2^{l - m}}}\)。
我们对所有给定的串\(S_i\)建立AC自动机。对于每个串\(S_i\)和\(S_j\)，我们希望求出所有的\(link({S_i},{S_j})\)集合元素。这等价于\(S_i\)对应的AC自动机中的结束状态开始沿fail指针向上走所能到达的所有状态（这一集合设为\(F(S_i)\)）中，有哪些状态在Trie树上是\(S_j\)对应结束状态的祖先。这样转化问题后，可以得到如下做法：
对于每个\(S_i\)，先求出\(F(S_i)\)；对于每个结点\(N \in F(S_i)\)，将Trie树上\(N\)的子树中所有结点均加上一个值\(2^{l - m}\)，最后对每个\(S_j\)，查询Trie树对应结束状态的值即可。树上子树增加单点查询显然可以按树的dfs序用树状数组维护。
事实上，还可以进一步优化。注意到子树修改完后才询问，因此可以使用差分来修改区间，修改完后再前缀和回答询问。但是注意到Trie树的结点很多（可达\(nm\)量级），不能每次对所有结点前缀和。然而幸运的是，我们的查询仅限于Trie树结束状态的结点，因此只需要对这些结点按dfs序生成一个长度为\(n\)的区间，修改时差分，询问时前缀和即可。
时间复杂度分析
最后分析时间复杂度。首先建立AC自动机时间复杂度\(O(nm)\)。求出Trie树结束状态的结点dfs序，以及每个树上结点对应的dfs序区间时间复杂度也是\(O(nm)\)。对每个\(S_i\)，求出\(F(S_i)\)然后差分修改的时间复杂度为\(O(m)\)，因为\(F(S_i)\)集合大小一定不超过\(m\)；最后前缀和并查询的时间复杂度为\(O(n)\)。全部求出后高斯消元的时间复杂度为\(O(n^3)\)。故总时间复杂度为\(O(n(m+n^2))\)。
总结
花了好几个小时才把理论推导理清楚，这题实在是太神了！同时对自己毒瘤的把数据范围改到\(m=10000\)表示成就感++（2333）！
AC代码
已略去高斯消元模板和AC自动机模板。
#define LETTER 2
inline int convert(char ch){ return ch == 'T' ? : ; }
int stEnd[], dfsEnd[], cnt2;
double a[], link[][];
int l[], r[];
char s[];
struct Trie{
int num, fail, match, depth;
int next[LETTER];
}pool[];
void insert(char *s, int id)
{
int cur = ;
for (int i = ; s[i]; i++){
int &pos = trie[cur].next[convert(s[i])];
if (!pos){
pos = ++cnt;
memset(&trie[cnt], , sizeof(Trie));
trie[cnt].depth = i + ;
}
cur = pos;
}
trie[cur].num = id;
}
void dfs(int i)
{
if (trie[i].num){
dfsEnd[trie[i].num] = ++cnt2;
l[i] = r[i] = cnt2;
}
else{ l[i] = << ; r[i] = ; }
for (int j = ; j<LETTER; j++){
int id = trie[i].next[j];
if (id){
dfs(id);
l[i] = min(l[i], l[id]);
r[i] = max(r[i], r[id]);
}
}
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
init();
for (int i = ; i <= n; i++){
scanf("%s", s);
insert(s, i);
stEnd[i] = cnt;
}
dfs();
makeFail();
for (int i = ; i <= n; i++){
memset(a, , sizeof(a));
for (int st = stEnd[i]; st; st = trie[st].fail){
double t = pow(, trie[st].depth - m);
a[l[st]] += t; a[r[st] + ] -= t;
}
for (int j = ; j <= n; j++)
a[j] += a[j - ];
for (int j = ; j <= n; j++)
link[i][j] = a[dfsEnd[j]];
}
Matrix mt(n + , n + );
for (int i = ; i <= n + ; i++)
mt.a[][i] = ;
for (int i = ; i <= n; i++){
mt.a[i][] = ;
for (int j = ; j <= n; j++)
mt.a[i][j] = link[j][i];
}
mt.gauss();
for (int i = ; i <= n; i++)
printf("%.10lf\n", mt.a[i][n + ]);
}