正题

题目链接:https://www.luogu.com.cn/problem/P8208

题目大意

给出\(n\)个点若干条边的一张图中,一个人在\(1\)开始随机游走\(t\)步。

如果他到达一个点他曾经到达过的点,那么就会产生它上次在这个点走向的点的编号的贡献。

求期望贡献。

\(1\leq n\leq 100,1\leq t\leq 100\)

解题思路

我们可以视为两次走到同一个点的时间之间会产生贡献,那么我们可以先预处理出\(f_{i,j}\)表示走了\(i\)步到达\(j\)的概率。

然后考虑再走回这个点,对于我们当前枚举的点\(x\),我们可以预处理出\(g_{i,j}\)表示从\(x\)出发走了\(i\)步,到达\(j\)时的概率乘上上次离开\(x\)点时贡献,那么我们取\(g_{i,x}\)就可以得到重复经过这个点时的贡献了。

时间复杂度:\(O(n^3t+n^2t^2)\)

解题思路

#include<cstdio>#include<cstring>#include<algorithm>#define ll long longusing namespace std;const ll N=110,P=998244353;ll n,s,T,m[N],v[N][N];ll ans,f[N][N],g[N][N],inv[N];ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans;}signed main(){scanf("%lld%lld%lld",&n,&s,&T);for(ll i=1;i<=n;i++){scanf("%lld",&m[i]);for(ll j=0,x;j<m[i];j++)scanf("%lld",&v[i][j]);inv[i]=power(m[i],P-2);}f[0][s]=1;for(ll j=0;j<T;j++)for(ll x=1;x<=n;x++)for(ll k=0;k<m[x];k++)(f[j+1][v[x][k]]+=f[j][x]*inv[x]%P)%=P;for(ll x=1;x<=n;x++){memset(g,0,sizeof(g));for(ll i=0;i<m[x];i++)g[0][v[x][i]]=v[x][i]*inv[x]%P;for(ll i=0;i<T-1;i++)for(ll j=1;j<=n;j++){if(j==x||!g[i][j])continue;for(ll k=0;k<m[j];k++)(g[i+1][v[j][k]]+=g[i][j]*inv[j]%P)%=P;}for(ll i=0;i<T;i++)for(ll j=0;j<T-i;j++)(ans+=f[i][x]*g[j][x]%P)%=P;}printf("%lld\n",ans);return 0;}