[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("
");
}
//#endif
gauss(n+1,n+2);
for(int i=1;i<=n;i++){
printf("%.10lf
",mat[i][n+2]);
}
}