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

显然对$n$个玩家的序列建立$ac$自动机

高斯消元

其实这是个无限循环游戏,因为轮次可以是无限的

我们直接定义$f[i]$表示最终停在自动机节点$i$的概率,下面的$p_{i,j}$表示节点$i$到节点$j$的概率

显然非终止节点的$f[i]=0$

至于求终止节点的$f[i]$,是从若干个非终止节点转移而来的,知道非终止节点的$f[j]$没有意义,无法转移

那我们变一下,定义$f[i]$表示经过节点$i$的概率

对于节点$i$来说,转移方程为$f[i]+=f[j]\ast p_{j,i}$,当然$j$不能是终止节点

对于根节点来说一开始就经过了根节点,$f[0]=1$

然后去高斯消元,发现$wa$了…

发现问题是根节点会转移出去,然后有一些节点又会回到根节点,这样到根节点的概率是不是还大于1了呢??

这使得定义出现问题,需要再次更换思路

定义$f[i]$为经过节点$i$的期望次数

那么对于终止节点来说,经过的期望其实就是概率

因为对于根节点,一开始就经过了一次,其中$p_{i,j}$表示$i$转移到$j$的概率

$f[0]=1+f[j]\ast p_{j,0}$

对于一般节点

$f[i]=f[j]\ast p_{j,i}$

高斯消元即可

#include 
   
    using namespace std;const int maxn = 1009;const double eps = 1e-9;int n,l,m;double p[maxn],mp[maxn][maxn];int zi[maxn][30],ID[maxn],id,fail[maxn],vis[maxn];char a[maxn];void insert(char a[],int index ){
   	int n = strlen( a+1 ), now = 0;	for(int i=1;i<=n;i++)	{
   		if( !zi[now][a[i]-'A'] )	zi[now][a[i]-'A'] = ++id;		now = zi[now][a[i]-'A'];	}	ID[index] = now; vis[now] = 1;}void make_fail(){
   	queue
    
     q;	for(int i=0;i
     
      > n >> l >> m;	for(int i=0;i
      
       > ( a+1 ); insert( a,i ); }	make_fail();	mp[0][id+1] = 1;	for(int i=0;i<=id;i++)	{
   		mp[i][i] = 1;		if( vis[i] )	continue;		for(int j=0;j
      
     
    
   

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