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)\)
完结撒花✿✿ヽ(°▽°)ノ✿
标签：题解,sum,Cnoi2020,cfrac,rightarrow,P6835,du,Sum,times From： https://www.cnblogs.com/Phrvth/p/17563401.html