本文共 1525 字，大约阅读时间需要 5 分钟。

设$x_0$表示经过一个任意长度,都没有任何人胜利的概率

$x_i$表示经过一个任意长度的串,最后$i$胜利的概率

考虑最后游戏结束,一定是由一个模式串$t$加上$s_i$形成的

因为形成$s_i$的概率是$\frac{1}{2^m}$,所以看上去$x_i=\frac{1}{2^m}\ast x_0$,但是显然没有这么多

但是这样不对,因为$t+s_i$串,在连接部分可能拼接一个串$s_j$使得更早结束游戏

也就是当$t$串的某个后缀加上$s_i$的某个前缀等于$s_j$时会更早的结束游戏

那我们可以枚举串$s_j$,枚举重复的前后缀长度,我们列出方程就是

$x_i+\sum _{j=1}^n{x}_j\ast (\sum _{k=1}^m[prefix(i,k)==suffix(j,k)]\ast \frac{1}{2^{m-k}})=\frac{1}{2^m}{x}_0$

上式可以理解为,如果串$s_j$的某个长度$k$的后缀是$s_i$的前缀

那么在$j$获胜的串后还需要添加长度$m-k$的$s_i$后缀,概率是$\frac{1}{2^{m-k}}$

累加就可以得到概率$\frac{1}{2^m}{x}_0$

这样就有$n$个方程组

#include 
   
    using namespace std;const long double eps = 1e-10;#define ULL unsigned long longconst ULL base = 131;const int maxn = 1009;long double mp[maxn][maxn],po[maxn];char s[maxn];int n,m;ULL p[maxn],suf[maxn][maxn],pre[maxn][maxn];void guass(int n){
   	for(int i=0;i<=n;i++)		{
   		int r = i;		for(int j=i+1;j<=n;j++)			if( fabs(mp[r][i])
    
     > n >> m;	p[0] = 1; po[0] = 1;	for(int i=1;i<=m;i++)	p[i] = p[i-1]*base,po[i] = po[i-1]*0.5;	for(int i=1;i<=n;i++)	{
   		cin >> ( s+1 );		for(int j=1;j<=m;j++)	pre[i][j] = pre[i][j-1]*base+s[j];	}	for(int i=1;i<=n;i++)	{
   		mp[i][i] = 1; mp[i][0] = -po[m];		for(int j=1;j<=n;j++)		{
   			for(int k=1;k
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/114592477 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！