线性生物

题解

题意

给定一个包含 n+1 个节点的有向图，节点编号为 1, 2, …, n+1。

• 基础边：对于所有 1 ≤ i ≤ n，存在一条有向边 i → i+1。
• 返祖边：额外给出 m 条有向边 u_i → v_i，其中 1 ≤ v_i ≤ u_i ≤ n。

从节点 1 出发，每一步等概率地选择当前节点的所有出边中的一条，并沿该边移动到下一个节点。
当到达节点 n+1 时，过程停止。

设随机变量 δ 表示从开始到停止所经过的总步数。
求 E(δ)（数学期望），结果对 998244353 取模后输出。

数据范围

• 0 < n, m ≤ 10^6
• 1 ≤ v_i ≤ u_i ≤ n
• id ∈ 5

题解

这是一道十分典型的期望$DP$的题目。

首先，对于期望函数$E(X)$我们有一个十分重要的性质

$E(a \cdot X+b \cdot Y)=a \cdot E(X)+b \cdot E(Y)$

这个性质是我们进行期望$DP$的重要支撑与基础，请牢记。

接下来我们开始尝试列出转移方程。

对于最直白的，我们设$f_i$表示从$1$走到$i$停止的数学期望。但是我们发现我们更本没必要这样做，由于期望函数的美好性质，我们只需要求出对于每个$i$从$i$走到$i+1$的期望步数就行了那么答案就是

$\sum_{i=1}^{n-1}E(i \to i+1)$

那么我们怎么求$E(i \to i+1)$呢？

这对于刚刚熟练掌握了数学期望的你是很简单的。

首先我们设$i$点的返租边的边集为$S$,那么首先我们有$\frac{1}{\left| S \right|+1}$的概率直接走$1$步基础边到$i+1$这个节点，那么我们的期望就是$\frac{1}{\left| S \right|+1}$

接下来枚举每一条返祖边$i \to v_j \in S$,首先我们有$\frac{1}{\left| S \right|+1}$的概率选到这条边并走出一步，然后在从$v_j$开始走到$i+1$根据期望是线性函数，我们可以知道$E(i \to v_j \to i+1)=E(i \to v_j)+E(v_j \to i+1)=E(i \to v_j)+\sum_{k=v_j}^{i} E(k \to k+1)$ 由于$k \leq i$所以我们就可以递推了，最后把每一条返祖边答案加起来即可。

我们设$f_i$表示$E(i \to i+1)$那么我们上面所说的转移方程如下：

$$f_i=\frac{1}{\left| S \right|+1}+\sum_{i \to v_i \in S}\frac{1}{\left| S \right|+1} \cdot (1+\sum_{k=v_j}^{i} f_k )$$

但是我们发现这个转移方程等式右边中有$f_i$的存在，所以我们要整理一下式子。

$$\begin{aligned} f_i &=\frac{1}{\left| S \right|+1}+\sum_{i \to v_i \in S}\frac{1}{\left| S \right|+1} \cdot (1+\sum_{k=v_j}^{i-1} f_k )+ \frac{\left| S \right|}{\left| S \right|+1} \cdot f_i \\ \frac{1}{\left| S \right|+1} \cdot f_i &=\frac{1}{\left| S \right|+1}+\sum_{i \to v_i \in S}\frac{1}{\left| S \right|+1} \cdot (1+\sum_{k=v_j}^{i-1} f_k ) \\ f_i &= 1+\sum_{i \to v_i \in S}(1+\sum_{k=v_j}^{i-1} f_k)\\ \end{aligned}$$

其中第二个求和项可以用前缀和处理，那么这个题就做完了

代码

code

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+10;
const ll mod=998244353;
int id,n,m;
vector<int> a[N];
ll sum[N];
ll f[N];
ll ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>id>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x].push_back(y);
    }
    for(int i=1;i<=n;i++) 
    {
        f[i]=1;
        for(int j=0;j<a[i].size();j++) 
        {   
            f[i]=(f[i]+1+((sum[i-1]-sum[a[i][j]-1])%mod+mod)%mod)%mod;
        }
        sum[i]=(sum[i-1]+f[i])%mod;
        ans=(ans+f[i])%mod;
    }
    cout<<ans;
    return 0;
}