随机游走问题

article/2025/8/23 16:20:40

随机游走指的是在一个点以等可能的概率走向下一个点。

问题1：

Link:https://www.luogu.com.cn/problem/P3232

题意：这道题其实相当于求每条边经过的期望次数。

思路：每条边经过的期望次数不好算，我们想到点经过的期望次数。于是有公式：

$f< u,v>=\frac{E(u)}{deg(u)}+ \frac{E(v)}{deg(v)}$

这个公式是显而易见的，它的含义是每条边经过的期望次数相当于从这条边的两个端点出发选择这条边的概率。于是我们就成功将这道题转化为求每个点经过的期望概率。而每个点经过的期望概率就是这个点由其直接相邻的点到达的期望。可能有点绕，但写成公式还是比较好理解的。

$E(u)=\displaystyle\sum_{e(u,v)\epsilon E}\frac{E(v)}{deg(v)}$

需要特别指明的是，1号节点由于是出发点，我们需要+1，以保证初始就经过1号节点这个条件。

初次之外，第n个点期望经过次数应该为0，否则就结束了。这种形式我们就可以写高斯消元了。

高斯消元的板子

void Gauss(int n,double **a,double *b,double *x)
{for(int i=1;i<=n;++i){int p=i;for(int k=i+1;k<=n;++k)if(fabs(a[k][i])>fabs(a[p][i]))p=i;if(i!=p)swap(a[i],a[p]),swap(b[i],b[p]);for(int k=i+1;k<=n;++k){double d=a[k][i]/a[i][i];b[k]-=d*b[i];for(int j=i;j<=n;++j)a[k][j]-=d*a[i][j];} }for(int i=n;i>=1;--i){for(int j=i+1;j<=n;++j)b[i]-=x[j]*a[i][j];x[i]=b[i]/a[i][i];}
}

ac代码

#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
const int mod=998244353;//1000000007;
const int inf=0x3f3f3f3f;
const int N=1e5+10;
const int M=5e5+10;
const int tt=(int)(log2(N))+1;
ll qcm(ll a,ll b,ll mod)
{ll res=1ll;while(b){if(b&1ll)res=res*a%mod;a=a*a%mod;b>>=1ll;}return res;
}
int bsgs(int a, int b, int mod)
{map<int, int> mp;int cur = 1, t = (int)sqrt(mod) + 1;for(int B = 0; B < t; ++B){mp[b*cur%mod] = B;cur = (ll)cur * a % mod;}int now = cur;for(int A = 1; A <= t; ++A){if(mp.find(now)!=mp.end()) return (ll)A * t - mp[now];now = (ll)now * cur % mod;}return -1;
}
void Gauss(int n,double a[][510],double *b,double *x)
{for(int i=1;i<=n;++i){int p=i;for(int k=i+1;k<=n;++k)if(fabs(a[k][i])>fabs(a[p][i]))p=i;if(i!=p)swap(a[i],a[p]),swap(b[i],b[p]);for(int k=i+1;k<=n;++k){double d=a[k][i]/a[i][i];b[k]-=d*b[i];for(int j=i;j<=n;++j)a[k][j]-=d*a[i][j];} }for(int i=n;i>=1;--i){for(int j=i+1;j<=n;++j)b[i]-=x[j]*a[i][j];x[i]=b[i]/a[i][i];}
} 
int a[510][510],deg[510];
double dp[510],aa[510][510],p[510];
double dd[125010];
void solve()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;++i){int x,y;scanf("%d%d",&x,&y);a[x][y]=a[y][x]=i;deg[y]++;deg[x]++;}p[1]=-1;for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){if(i==j)aa[i][j]=-1;else if(a[i][j])aa[i][j]=(double)1/deg[j];}}Gauss(n-1,aa,p,dp);for(int i=1;i<=n;++i){for(int j=i+1;j<=n;++j){if(!a[i][j])continue;dd[a[i][j]]=dp[i]/deg[i]+dp[j]/deg[j];}}sort(dd+1,dd+m+1);double ans=0;for(int i=1;i<=m;++i)ans+=dd[i]*(m-i+1);printf("%.3lf\n",ans);
}
void init()
{}
int main()
{int T=1;//init();//scanf("%d",&T);while(T--)solve();return 0;
}