题解 P6835 【[Cnoi2020]线形生物】
tiger2005
2020-09-27 16:47:12
## 题意简述
有 `N+1` 个点，从 `i` 指向 `i+1` 形成一个链，其中还有一些返祖边。
一个生物在 `1` 号点，每次将随机选择一条边通过，求出走到 `N+1` 的步数期望。
## 分析
神奇做法注意！
先推式子。假设 $f_x$ 表示 `x` 走到 `N+1`的期望步数。
$$f_x=\dfrac{\sum\limits_{(x,u)\in E}f_u+1}{\sum\limits_{(x,u)\in E}1}=\dfrac{\sum\limits_{(x,u)\in E}f_u}{\operatorname{outDegree}(x)}+1$$
这个式子的分子中只有 `x+1` 一个数大于 `x`，可以代入 $f_{x+1}$ 的表达式算 $f_x$。
$$f_x=\dfrac{\sum\limits_{(x,u)\in E}f_u}{\operatorname{outDegree}(x)}+1=\dfrac{f_{x+1}}{\operatorname{outDegree}(x)}+\dfrac{\sum\limits_{(x,u)\in E \operatorname{and} u \leq x}f_u}{\operatorname{outDegree}(x)}+1$$
那就可以把 $f_{x+1}$ 的表达式写成一个数组 `g`，满足$f_{x+1}=g_{const}+\sum f_i \times g_i$，然后每次把这个数组除上 $\operatorname{outDegree}(x)$，然后把返祖边对应位置加上 $\dfrac{1}{\operatorname{outDegree}(x)}$，然后常数项加上 1。但是算完之后要把值算出来了，那就只能算的时候消元了。
$f_{x+1}=g_{const}+\sum f_i \times g_i=g_{const}+\sum\limits_{i \in [1,x]}f_i \times g*i+f_{i+1}*g_{i+1}$
$(1-g_{x+1})f_{x+1}=g_{const}+\sum\limits_{i \in [1,x]}f_i \times g_i$
$f_{x+1}=\dfrac{g_{const}+\sum\limits_{i \in [1,x]}f_i \times g_i}{1-g_{x+1}}$
然后就可以把当前点的系数消掉了！
但是这么算超时是无法避免的，那怎么办呢？
想到超时的真正原因是区间除的时候使用暴力方法，那么可以使用类似于 `tag` 的思想。对于一个数组 `s` ，可以将修改变成如下形式：
```
tag=1;
divideBy(a) -> tag*=a;
addNumber(a,x) -> s[a]+=x*tag;
getValue(a) -> return a/tag;
```
然后这道题就可以在 $O(n+m)$ 的复杂度内作完，就是算逆元常数有点大。
## 代码
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
inline int read(){
register int ret=0;
char ch=getchar();
while(ch<'0') ch=getchar();
while(ch>='0') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();
return ret;
}
vector<int> To[1000010];
const long long Md=998244353;
int N,M;
inline long long ksm(int x,int y){
register long long ret=1,bas=x;
while(y){
if(y&1) (ret*=bas)%=Md;
(bas*=bas)%=Md;y>>=1;
}
return ret;
}
long long SZ[1000010],MUL=1,DIV=1;
inline void add(int x,long long a){
(SZ[x]+=a*DIV%Md)%=Md;
}
int main(){
read();N=read();M=read();
for(int i=1,u,v;i<=M;i++){
u=read();v=read();
To[u].push_back(v);
}
SZ[0]=0;
register long long L,P,Q;
for(int i=N;i;i--){
L=To[i].size()+1;
P=ksm(L,Md-2);
(MUL*=P)%=Md;(DIV*=L)%=Md;
for(int j=0;j<To[i].size();j++)
add(To[i][j],P);
add(0,1);
Q=(1+Md-SZ[i]*MUL%Md)%Md;
(MUL*=ksm(Q,Md-2))%=Md;(DIV*=Q)%=Md;
SZ[i]=0;
}
printf("%lld",(SZ[0]*MUL)%Md);
}
```