自动搬运

查看原文

来自洛谷，原作者为

	tommymio Cruel world

搬运于2025-08-24 22:24:27，当前版本为作者最后更新于2020-09-29 10:22:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

期望入门题。

这题非常的好，考察了期望的线性性质和选手的推柿子能力，给良心出题人点赞（然而我月赛时并没有做出来

注：期望的线性性质：在本题中体现为从 $x$ 点到 $y$ 点的期望步数 $E_{x\to y}=E_{x\to x+1}+...+E_{y-1 \to y}=\sum\limits_{i=x}^{y-1}E_{i\to i+1}$。

对于这类在图上随机游走的问题，我们一般会设 $E_{x\to x+1}$ 表示从 $x$ 点到 $x+1$ 点的期望步数，那么答案就是 $\sum\limits_{x=0}^n E_{x\to x+1}$ 的值。

不妨先根据期望的定义列出 $E_{x\to x+1}$ 的转移式（其中 $du_x$ 表示 $x$ 的返祖边的条数，而 $E$ 表示 $x$ 的返祖边的边集）：

$$E_{x\to x+1}=\frac{1}{du_x+1}\times1+\frac{1}{du_x+1}\sum_{(x,y)\in E} (E_{y\to x+1}+1) $$

将 $E_{y\to x+1}=\sum\limits_{i=y}^{x}E_{i\to i+1}$ 代入上式并对上式进行化简：

$$E_{x\to x+1}=1+\frac{1}{du_x+1}\sum_{(x,y)\in E}\sum_{i=y}^xE_{i\to i+1} $$

此时记 $E_{x\to x+1}$ 为 $f_x$，记 $sum_x=\sum\limits_{i=0}^x f_i$，则上式可写作：

$$f_x=1+\frac{1}{du_x+1}\sum_{(x,y)\in E}sum_x-sum_{y-1} $$

发现等式两边都含有 $E_{x\to x+1}$ ，把 $E_{x\to x+1}$ 全部提到左边（为了让 $f_x$ 能够转移），并消去和式系数 $\frac{1}{du_x+1}$，得：

$$f_x=(du_x+1)+\sum_{(x,y)\in E}sum_{x-1}-sum_{y-1}$$

到这里维护一下前缀和，就可以直接转移了。总时间复杂度为 $O(n)$。

上式的化简步骤都是一些常见的状态转移方程的 $\text{Dirty Work}$，本来不想写出来的（

Show the Code

#include<cstdio>
#define int ll
typedef long long ll;
const int mod=998244353;
int cnt=0;
int h[1000005],to[2000005],ver[2000005];
int f[1000005],sum[1000005],du[1000005];
inline int read() {
	register int x=0,f=1;register char s=getchar();
	while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
	while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
	return x*f;
}
inline void add(int x,int y) {to[++cnt]=y;ver[cnt]=h[x];h[x]=cnt;}
signed main() {
	int id=read(),n=read(),m=read();
	for(register int i=1;i<=m;++i) {int x=read(),y=read();add(x,y);++du[x];}
	for(register int x=1;x<=n;++x) {
		f[x]=du[x]+1;
		for(register int i=h[x];i;i=ver[i]) {
			int y=to[i];
			f[x]=((f[x]+(sum[x-1]-sum[y-1])%mod)%mod+mod);
		}
		sum[x]=(sum[x-1]+f[x])%mod;
	}
	printf("%lld\n",sum[n]); 
	return 0;
}