【题意】
给定n个小朋友每个人有一个01串,游戏规则如下,每次在一个生成的串的末尾随机生成0/1,当出现了某个小朋友手里的串的时候游戏结束,该小朋友获胜,求每个小朋友获胜的概率是多少
【分析】
这道题目其实就是P6125 [JSOI2009]有趣的游戏的加强版
考虑有趣的游戏这道题的方式为AC自动机dp,上面有很多无用的点也被计算在内了,时间复杂度无法接受‘
所以我们继续考虑别的方式
很明显,游戏结束时的串一定是以一个小朋友手里的串结尾的
我们想去通过构造串的方式进行计算概率
设x0为生成一个不包含任何小朋友手里的串的概率,先不考虑这个怎么求
我们发现x0+ai可以为结束的串,ai指的是小朋友i的串
对于每个长度为len的串,出现的概率都是$\frac{1}{2^{len}}$
但是这样算会出现一点问题,就是x0串的末尾和xi串的开头可能拼成了一个aj,导致在出现x0+ai之前游戏就结束了
我们计算xi的时候就要减去这些概率
所以可以列出方程如下
$x_i+\sum_{j=1}^{n}\sum_{len=1}^{m-[i==j]}[pre_{x_i,len}=suf_{x_j,len}]\frac{1}{2^{m-a}}=\frac{1}{2^m}x_0$这里$pre_{x_i,len}$表示i串的len长度的前缀
这里的前缀和另一个的后缀是否相等用hash判断即可
列出方程后进行高斯消元
【代码】
#include<bits/stdc++.h> using namespace std; int s[305][305]; char ss[305]; int n,m; double A[303][303],p[303],res[303]; int has[303][303],bb[303]; const int base=13131; const int mod=1e9+7; void guass(int n) { for(int i=1;i<=n;i++) { int pos=i; for(int j=i;j<=n;j++) if(fabs(A[j][i])>fabs(A[pos][i])) pos=i; for(int j=1;j<=n+1;j++) swap(A[pos][j],A[i][j]); for(int j=1;j<=n;j++) { if(i!=j) { double t=A[j][i]/A[i][i]; for(int k=i+1;k<=n+1;k++) A[j][k]-=A[i][k]*t; } } } for(int i=1;i<=n;i++) res[i]=A[i][n+1]/A[i][i]; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%s",ss+1); for(int j=1;j<=m;j++) s[i][j]=(ss[j]=='T'?0:1); } p[0]=1.0; bb[0]=1; for(int i=1;i<=m;i++) p[i]=p[i-1]*0.5; for(int i=1;i<=m;i++) bb[i]=bb[i-1]*base; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) has[i][j]=1LL*has[i][j-1]*base+s[i][j]; for(int i=1;i<=n;i++) { A[i][n+1]=-p[m]; A[i][i]=1.0; for(int j=1;j<=n;j++) { for(int len=1;len<=m-(i==j);len++) if(has[i][len]==has[j][m]-has[j][m-len]*bb[len]) A[i][j]+=p[m-len]; } } for(int i=1;i<=n;i++) A[n+1][i]=1.0; A[n+1][n+2]=1.0; // for(int i=1;i<=n+1;i++) // { // for(int j=1;j<=n+1;j++) // printf("%.3f ",A[i][j]); // printf("= %.3f\n",A[i][n+2]); // } guass(n+1); for(int i=1;i<=n;i++) printf("%.10f\n",res[i]); return 0; }