【题解】 [Cnoi2020]线形生物 期望dp

Legend

Link ( extrm{to Luogu})。

给定 (1 o 2 o cdots o n o n+1) 的边和 (m) 条往回走的有向边，长度都是 (1)。站在一个点时等概率选择一条出边，求 (1 o n+1) 期望长度。

(1 le n ,m le 10^6)。

Editorial

考虑一个套路：设 (f_{i}) 表示从 (i) 走到 (i+1) 行走总距离的期望，答案就是 (sumlimits_{i=1}^n f_i)。

$f_i = dfrac{1}{d_i} sumlimits_{(i,j) in G land j < i} S_{i,j-1} + f_i $，其中 (S_{i,j}) 表示 (sumlimits_{k=i}^{j} f_i)

(f_i) 前缀和可以在转移过程中一并算出，所以复杂度就是 (O(n))。

Code

代码采用了 (O(log p)) 的快速幂求逆元，所以复杂度是 (O(n log p)) 的。

#include <bits/stdc++.h>

#define LL long long

int read(){
	char k = getchar(); int x = 0;
	while(k < '0' || k > '9') k = getchar();
	while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
	return x;
}

const LL MOD = 998244353;
LL qpow(LL a ,LL b ,LL p = MOD){
	LL Ans = 1;
	while(b){if(b & 1) Ans = Ans * a % p;
		a = a * a % p ,b >>= 1;
	}return Ans;
}

const int MX = 1e6 + 233;
LL dp[MX] ,zh[MX] ,qzh[MX];
int n ,m;
std::vector<int> fz[MX];

int main(){
	read();
	n = read() ,m = read();
	for(int i = 1 ,u ,v ; i <= m ; ++i){
		u = read() ,v = read();
		if(u != v)	fz[u].push_back(v);
		else zh[u]++;
	}
	LL Ans = 0;
	for(int i = 1 ; i <= n ; ++i){
		int ch = fz[i].size() + 1 + zh[i];
		LL inv = qpow(ch ,MOD - 2);
		dp[i] = 1;
		for(auto j : fz[i]){
			dp[i] = (dp[i] + inv * (qzh[i - 1] - qzh[j - 1] + MOD)) % MOD;
		}
		dp[i] = dp[i] * ch % MOD;
		// printf("f[%d] = %lld
" ,i ,dp[i]);
		Ans = (Ans + dp[i]) % MOD;
		qzh[i] = (qzh[i - 1] + dp[i]) % MOD;
	}
	using namespace std;
	cout << Ans << endl;
	return 0;
}