P6835 [Cnoi2020]线形生物
tongyf
2020-09-19 20:12:50
评价：很好的一道期望DP，防止了期望DP“设从当前到终点期望为状态”的惯性思维
---
[题面](https://www.luogu.com.cn/problem/P6835)
思路：
我们发现按照上面提到的惯性思维设$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
解释一下转移方程：
$\sum^{i}_{k=pre(i,j)}f(k)$是因为有可能返祖，然后要从返祖边的目标点回来，$+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$
$\sum^{i-1}_{k=pre(i,j)}$可以前缀和优化
时间复杂度$O(n+m)$
代码：
```cpp
#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;
}
```