P6835 [Cnoi2020]线形生物

· · 题解

评价：很好的一道期望DP，防止了期望DP“设从当前到终点期望为状态”的惯性思维

题面

思路：

我们发现按照上面提到的惯性思维设f(i)为从i到n+1期望步数为状态根本无法转移，因为有后效性

那么怎么样没有后效性呢？

我们设f(i)为从i到i+1期望步数

那么有转移方程：

f(i)=\frac{\sum^{du}_{j=1} ((\sum^{i}_{k=pre(i,j)}f(k))+1)}{du}

其中du为当前点出边数+1

解释一下转移方程：

当$j=du$时$\sum^{i}_{k=pre(i,j)}f(k)=0

化简一下上面的转移方程：

f(i)=\frac{(\sum^{du}_{j=1} \sum^{i-1}_{k=pre(i,j)}f(k))+(du-1)*f(i)}{du}+1 (1-\frac{du-1}{du})f(i)=\frac{\sum^{du}_{j=1} \sum^{i-1}_{k=pre(i,j)}f(k)}{du}+1 f(i)=\sum^{du}_{j=1} \sum^{i-1}_{k=pre(i,j)}f(k)+du 时间复杂度$O(n+m)

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int id,n,m,f[1000005],sum[1000005];
vector<int> e[1000005];
int read(){
    int f=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        f=f*10+ch-'0';
        ch=getchar();
    }
    return f*w;
}
signed main(){
    id=read(),n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        e[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<e[i].size();j++){
            f[i]=((f[i]+sum[i-1]-sum[e[i][j]-1])%mod+mod)%mod;
        }
        f[i]=(f[i]+e[i].size()+1)%mod;
        sum[i]=(sum[i-1]+f[i])%mod;
    }
    printf("%lld\n",sum[n]);
    return 0;
}