正題

題目鏈接:https://www.luogu.com.cn/problem/P6835?contestId=34123

---

題目大意

$n+1$個點，其中每個$i$向$i+1$連邊$(i\le n)$，然后有$m$對$(u,v)$表示$u$向$v$連邊$u\ge v$。開始在點$1$，每次隨機走一個相連的點。求到$n+1$號點的期望步數。

---

解題思路

就是沒有后效性的隨機游走，設$f_i$表示$i$號點走向$i+1$號點的期望步數，$z$表示出度，我們就有方程$$f_i=\frac{{\sum }_{i?>j}({\sum }_{k=j}^{i?1}{f}_k)+f_i}{z}+1$$
我們將$\frac{(z?1)?f_i}{z}$提出就有
$$f_i?\frac{(z?1)}{z}{f}_i=\frac{{\sum }_{i?>j}({\sum }_{k=j}^{i?1}{f}_k)}{z}+1$$
$$?f_i=\sum _{i?>j}(\sum _{k=j}^{i?1}{f}_k)+z$$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e6+10,XJQ=998244353; struct node{ll to,next; }a[N*2]; ll n,m,tot,ls[N],p[N],f[N],sum[N]; void addl(ll x,ll y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } int main() {ll id;scanf("%lld%lld%lld",&id,&n,&m);for(ll i=1;i<=m;i++){ll x,y;scanf("%lld%lld",&x,&y);addl(x,y);}for(ll x=1;x<=n;x++){ll z=1;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;z++;f[x]=(f[x]+sum[x-1]-sum[y-1]+1+XJQ)%XJQ;}f[x]=(f[x]+1)%XJQ;sum[x]=(sum[x-1]+f[x])%XJQ;}printf("%lld",sum[n]); }

總結

以上是生活随笔為你收集整理的P6835-[Cnoi2020]线形生物【期望dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。