oj:https://gxyzoj.com/d/hzoj/p/P451
概率与期望+hash+高斯消元
声明一些东西，pre(S,l)表示串S的长度为l的前缀，lst(S,l)表示串S的长度为l的后缀
一. 对于所有串建立字典树，像「HNOI2013」游走 一样高斯消元，时间复杂度 \(O(n^3m^3)\) ，预计50/70pts
二. 正解：
-
显然，n项中，出现一个长度为n的串s的概率为 \(\frac{1}{2^n}\)
-
先从部分分入手，当n=2时，设两串A=101，B=110，有一个不含这两个串的串S，显然，在S后直接加上A，概率\(\frac{1}{8}\)，游戏结束。
但有一些特殊情况：
（1）S的结尾是10，则再加上1则会出现A串，游戏结束，概率\(\frac{1}{2}\)
（2）S的结尾是1，则再加上10则会出现B串，游戏结束，概率\(\frac{1}{4}\)
（3）其余情况，第一个人获胜
故\(\frac1 8 S=\frac1 4A+\frac1 2B+A\)
同理，可得加上B的情况，得 \(\frac1 8 S=\frac1 4A+B\)
解得\(A=\frac2 3,B=\frac1 3\)
从中，可得到只有2个串的式子：
\[\frac{1}{2^m}S=\sum_{pre(A,i)=lst(A,i)}x_A\times \frac{1}{2^{m-i}}+\sum_{pre(A,i)=lst(B,i)}x_B\times \frac{1}{2^{m-i}} \]按照如上方法，可列出关于B的式子
依题意得：\(x_A+x_B=1\)，三个式子，三个未知数，可以高斯消元
- 推广2的式子，可以得到：
高斯消元求解即可
警示后人：注意eps的大小，最好设成\(10^{-300}\)，这题卡精度！！！
- 代码：
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#define ull unsigned long long
using namespace std;
int n,m,q=2;
ull pre[305][305],p1[305];
string s[305];
double a[305][305],p[305],eps=1e-300;
void guass()
{
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if(fabs(a[i][i])<fabs(a[j][i]))
{
swap(a[i],a[j]);
}
}
if(fabs(a[i][i])>eps)
{
for(int j=n+1;j>=i;j--)
{
a[i][j]/=a[i][i];
}
for(int j=i+1;j<=n;j++)
{
for(int k=n+1;k>=i;k--)
{
a[j][k]-=a[j][i]*a[i][k];
}
}
}
}
for(int i=n-1;i>0;i--)
{
for(int j=i+1;j<=n;j++)
{
a[i][n+1]-=a[i][j]*a[j][n+1];
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i]=" "+s[i];
for(int j=1;j<=m;j++)
{
if(s[i][j]=='H') s[i][j]=0;
else s[i][j]=1;
pre[i][j]=pre[i][j-1]*q+s[i][j];
}
}
p[0]=p1[0]=1;
for(int i=1;i<=m;i++)
{
p1[i]=p1[i-1]*q;
p[i]=p[i-1]*0.5;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int l=1;l<=m;l++)
{
if(pre[i][l]==pre[j][m]-pre[j][m-l]*p1[l])
{
// printf("%d %d %d\n",i,j,l);
a[i][j]+=p[m-l];
}
}
}
}
for(int i=1;i<=n;i++) a[i][n+1]=-p[m];
for(int i=1;i<=n;i++) a[n+1][i]=1;
a[n+1][n+2]=1;
n++;
// for(int i=1;i<=n+1;i++)
// {
// for(int j=1;j<=n+2;j++)
// {
// printf("%.10lf ",a[i][j]);
// }
// printf("\n");
// }
guass();
for(int i=1;i<n;i++)
{
printf("%.10lf\n",a[i][n+1]);
}
return 0;
}