[BZOJ 4820] [SDOI2017] 硬币游戏(高斯消元+概率论+字符串hash)
题面
扔很多次硬币后,用H表示正面朝上，用T表示反面朝上，会得到一个硬币序列。比如HTT表示第一次正面朝上，后两次反面朝上。
选出n个同学，每个同学猜一个长度为m的序列，当某一个同学猜的序列在硬币序列中出现时(匹配时的序列必须连续)，就不再扔硬币了，并且这个同学胜利。猜的n个序列两两不同。
假设硬币正反面朝上的概率相同，求每个同学胜利的概率。
\(n \leq 300\)
分析
(注意，本题中不区分序列和串，因为只讨论连续的情况)
设与所有猜的序列都不匹配的串S期望长度是H(这个定义比较玄学，虽然是无限抛下去的，但是理解的时候当成有限长度抛出这种不匹配的情况比较好理解)
引理: 结尾包含一个长度为L的确定的串但没有包含任意一个给定序列的概率为\(\frac{1}{2^L}\).
感性理解一下就好了，证明略.
那么在这样的S串后面加上第i个人猜的串\(A_i\),那么\(SA_i\)就有可能成为一个胜利的状态。根据引理，抛出\(SA_i\)的概率为\(\frac{H}{2^m}\)。但是，有可能提前抛出其他的串。如\(S=\mathrm{HTH},A_1=\mathrm{HTT},A_2=\mathrm{THT}\),那么当串为\(\mathrm{HTHT}\)时,在抛出\(A_1\)之前就会抛出\(A_2\).同样，如果S本来就包含\(A_i\)的一部分,也可能提前抛出\(A_i\)导致提前胜利。把提前胜利的情况从\(\frac{H}{2^m}\)里减掉，就可以得到第i个人在抛出\(SA_i\)时胜利的概率。
注意到如果提前抛出串\(A_j\),那么\(A_i\)的某个前缀和\(A_j\)的某个后缀一定相等(可能不止1个)，比如HTT和THT的公共前后缀为TH。
设第\(i\)个人胜利的概率为\(p_i\),\(pre(S,i)\)表示串S长度为i的前缀，\(suf(S,i)\)表示串S长度为i的后缀。那么有
\]
解释一下\(\sum_{k=1}^{m-[i=j]} [pre(A_i,k)=suf(A_j,k)]\frac{1}{2^{m-k}}\)
我们枚举公共前后缀的长度k,当k确定时,\(pre(A_i,k)\)确定，那么后面长度为\(m-k\)的后缀也确定了。根据引理，这样的概率为\(\frac{1}{2^{m-k}}\)。
\(m-[i=j]\)的意义是, 当\(i=j\)时长度<=m-1时才是提前结束，如果长度为m,就是胜利的状态了。当\(k=m\)时,\([pre(A_i,k)=suf(A_i,k)]p_i \frac{1}{2^{m-k}}=p_i\),因此可以把左边的\(p_i\)去掉，然后把循环上界改成\(m\)
\]
移项,
\]
对于每个i，我们都可以得到这样一个方程。现在我们有\(p_1,p_2 \dots p_n,H\)共n+1个未知数,有n个方程.又因为\(\sum_{i=1}^n p_i=1\),我们就有n+1个方程了,直接高斯消元即可.suf和pre可以用哈希求。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define eps 1e-10
#define maxn 300
#define maxm 300
using namespace std;
typedef long long ll;
typedef double db;
int n,m;
char a[maxn+5][maxm+5];
const ll seed=2;
const ll mod=998244353;
ll hs[maxn+5][maxm+5];
ll pows[maxn+5];
db pow2[maxn+5];
void ini_hash(){
pow2[0]=1;
for(int i=1;i<=m;i++) pow2[i]=pow2[i-1]*0.5;
pows[0]=1;
for(int i=1;i<=m;i++) pows[i]=pows[i-1]*seed%mod;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) hs[i][j]=(hs[i][j-1]*seed+(a[i][j]=='T'))%mod;
}
}
db calc(int x,int y){
db ans=0;
for(int i=1;i<=m;i++){
if(hs[x][i]==(hs[y][m]-hs[y][m-i]*pows[i]%mod+mod)%mod) ans+=pow2[m-i];
}
return ans;
}
db mat[maxn+5][maxm+5];
void gauss(int n,int m){
for(int i=1;i<=n;i++){
int id=i;
for(int j=i+1;j<=n;j++){
if(mat[j][i]>mat[id][i]) id=j;//把系数最大的行j交换到第i行
}
for(int k=1;k<=m;k++) swap(mat[i][k],mat[id][k]);
for(int j=1;j<=n;j++){
if(i==j) continue;
db r=mat[j][i]/mat[i][i];//把第j行第i个未知数的系数消成0
for(int k=i;k<=m;k++) mat[j][k]-=mat[i][k]*r;
}
}
for(int i=1;i<=n;i++){
mat[i][m]/=mat[i][i];
}
}
int main(){
//#ifdef LOCAL
// freopen("game5.in","r",stdin);
//#endif
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",a[i]+1);
}
ini_hash();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
mat[i][j]=calc(i,j); //1/2^(m-a)
}
mat[i][n+1]=-pow2[m];//H也是未知数
mat[i][n+2]=0;
}
for(int i=1;i<=n;i++) mat[n+1][i]=1;//sum(p[i])=1
mat[n+1][n+2]=1;
//#ifdef DEBUG
for(int i=1;i<=n+1;i++){
for(int j=1;j<=n+2;j++) printf("%.4f ",mat[i][j]);
printf("\n");
}
//#endif
gauss(n+1,n+2);
for(int i=1;i<=n;i++){
printf("%.10lf\n",mat[i][n+2]);
}
}