P6835 [Cnoi2020] 线形生物题解

题目描述

求从 \(1\) 到 \(n+1\) 的链的期望，其中有 \(m\) 条返祖边：\(u->v\) 这条边 \(u\ge v\)，等概率，求期望

Solution

这种爬楼梯的题一般求解 \(E(x\rightarrow x+1)\)，则最后答案为 \(\sum_{i=1}^n E(i\rightarrow i+1)\)

我们考虑从 \(x\rightarrow x+1\)，可以有多少种情况（注意，一定从 \(x\) 开始）

\(x\) 选择了树边，则期望步数为 \(1\) 步，概率为 \(P(树边)=\cfrac{1}{du_x+1}\)，其中 \(du_x\) 为 \(x\) 的返祖边数量
\(x\) 选择了返祖边，则期望步数为：先走到那个点，然后再跳上来 \(1+E_{(x,y)\in G} (y\rightarrow x+1)\)，概率为 \(P(返祖边)=\cfrac{1}{du_x+1}\)

当然，有 \(du_x\) 条返祖边，我们把他加起来再把概率提出来可以得到一个基础式子：

\[E(x\rightarrow x+1)=\cfrac{1}{du_x+1}\times 1 + \cfrac{1}{du_x+1} \times \sum_{(x,y)\in G} E(y\rightarrow x+1) + 1 \]

考虑到右边的 \(E\) 不是一步一步，而是多步，我们根据期望的线性性可以得到一个拆解的式子：

\[E(x\rightarrow y)=\sum_{i=x}^{y-1} E(i\rightarrow i+1) \]

将这个式子带入上边，并且设 \(f(x)=E(x\rightarrow x+1)\) 则

\[f(x)=\cfrac{1}{du_x+1} + \cfrac{1}{du_x+1} \times \sum_{(x,y) \in G} (\sum_{i=y}^x (f(i))+1) \]

将 1 拆出来合并则：

\[\begin{aligned} f(x)=&\cfrac{1}{du_x+1}+\cfrac{1}{du_x+1}\times \sum_{(x,y)\in G}\sum_{i=y}^x f(i) + \cfrac{1}{du_x+1}\times du_x\\ =&\cfrac{du_x+1}{du_x+1} +\cfrac{1}{du_x+1}\times \sum_{(x,y)\in G}\sum_{i=y}^x f(i)\\ =& 1+\cfrac{1}{du_x+1}\times \sum_{(x,y)\in G}\sum_{i=y}^x f(i) \end{aligned} \]

注意到右边也有 \(f(x)\)，我们把它分离出来再用前缀和 \(Sum_x=\sum_{i=1}^x f(i)\) 优化一下：

\[f(x)=1+\cfrac{1}{du_x+1}\times \sum_{(x,y)\in G} Sum_{x-1}-Sum_{y-1} + \cfrac{1}{du_x+1}\times du_x \times f(x) \]

最后化简一下得到：

\[f(x)=du_x+1 + \sum_{(x,y)\in G} Sum_{x-1}-Sum_{y-1} \]

这是个非常完美的地递推式，写出代码：

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 7;

typedef long long ll;

const ll Mod = 998244353;

int id, n, m;

vector <int> G[MAXN];

ll Dp[MAXN], Sum[MAXN];

int main () {
	cin >> id >> n >> m;
	for (int i = 1, u, v; i <= m; i ++) {
		cin >> u >> v; G[u].push_back(v);
	}
	for (int i = 1; i <= n; i ++) {
		Dp[i] = 1;
		for (auto v : G[i]) 
			Dp[i] = (Dp[i] + Sum[i - 1] - Sum[v - 1] + 1 + Mod) % Mod;
		Sum[i] = (Sum[i - 1] + Dp[i]) % Mod;
	}
	cout << Sum[n] << '\n';
	return 0;
}

因为每个点每条边各枚举一次，总时间复杂度为 \(O(n+m)\)

完结撒花✿✿ヽ(°▽°)ノ✿