显然是期望 $\texttt{dp}$。

设 $f_i$ 为 $i$ 到 $i+1$ 的期望步数，$s_i=\sum\limits_{j=0}^{i}f_j$，$f_0=0$，$d_i$ 为 $i$ 点出度。 则有： \(f_{i}=\frac{1+\sum\limits_{i\rightarrow j}(f_{i}+s_{i-1}-s_{j-1}+1)}{d_{i}}\) 注： $j \ne i+1$

其实就是分类讨论， $\dfrac {1} {d_i}$ 为直接前进不回头的贡献。$\dfrac{f_{i}+s_{i-1}-s_{j-1}+1}{d_i}$ 为先往回走的贡献，即回到 $j$（$1$），再从 $j$ 走回 $i$（$s_{i-1}-s_{j-1}$），再继续向 $i+1$ 前进（$f_i$）。

化简得：

\(f_id_i=(d_i-1)f_i+(d_i-1)s_{i-1}+d_i-\sum\limits_{i\rightarrow j} s_{j-1}\) \(f_i=(d_i-1)s_{i-1}+d_i-\sum\limits_{i\rightarrow j} s_{j-1}\)

我们发现这个式子是无后效性的，可以递推。

时间复杂度

$\mathrm{O(n+m)}$，容易证明，我们会访问每条边恰好一次，并求出所有 $f_i\ (i\le n)$ 的值。

代码

#include<cstdio>
int const mod=998244353;
int id,n,m,head[1000010],to[1000010],nxt[1000010],cnt,d[1000010];
long long f[1000010],s[1000010];
void add(int const &x,int const &y){
	to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt,++d[x];
}
int main(){
	scanf("%d%d%d",&id,&n,&m);
	for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),add(x,y);
	for(int i=1;i<=n;i++){
		f[i]=d[i]*s[i-1]+d[i]+1;
		for(int j=head[i];j;j=nxt[j])f[i]-=s[to[j]-1];
		f[i]=(f[i]%mod+mod)%mod;
		s[i]=(s[i-1]+f[i])%mod;
	}
	printf("%lld",s[n]);
	return 0;
}