P6835

· · 个人记录

[Cnoi2020]线形生物

期望 DP。

因为可以在图上随机游走，直接以点为状态转移有些困难。

定义 E_{x\rightarrow y} 表示从 x 到 y 的期望步数，假设 x<z<y，那么就会有 E_{x\rightarrow y}=E_{x\rightarrow z}+E_{z\rightarrow y}（因为这里只有返祖），然后就能得到 E_{x\rightarrow y}=\sum_{i=x}^{y-1}E_{i\rightarrow i+1}。

然后我们定义 AE_i 为 i 的返祖边指向的点集，ae_i 表示返祖边条数（Atavistic Edge）。

然后就有转移：

E_{i\rightarrow i+1}=\dfrac{1}{ae_i+1}+\dfrac{1}{ae_i+1}\sum_{j\in AE_i}(E_{j\rightarrow i+1}+1)

然后我们根据 E_{x\rightarrow y}=\sum_{i=x}^{y-1}E_{i\rightarrow i+1} 把 E_{j\rightarrow i+1} 展开，带入原式并化简可以得到：

E_{i\rightarrow i+1}=1+\dfrac{1}{ae_i+1}\sum_{j\in AE_i}\sum_{k=j}^{i}E_{k\rightarrow k+1}

显然我们可以前缀和化简。定义 c_x=\sum_{i=1}^{x}E_{i\rightarrow i+1}，那么就会有：

E_{i\rightarrow i+1}=1+\dfrac{1}{ae_i+1}\sum_{j\in AE_i}(c_i-c_{j-1})

然后我们把 c_i 中的 E_{i\rightarrow i+1} 提取出来，得到：

E_{i\rightarrow i+1}=1+\dfrac{1}{ae_i+1}\sum_{j\in AE_i}(c_{i-1}-c_{j-1})+\dfrac{ae_i\cdot E_{i\rightarrow i+1}}{ae_i+1}

移项，再把左边的系数化为 1，就能得到：

E_{i\rightarrow i+1}=ae_i+1+\sum_{j\in AE_i}(c_{i-1}-c_{j-1})

这时我们发现，递推所需要的期望只有相邻两个点之间的期望了，所以我们干脆定义 f(i)=E_{i\rightarrow i+1}，则 c_i=\sum_{j=1}^if(i)。

于是就得到了一个很线性的转移方程：

f(i)=ae_i+1+\sum_{j\in AE_i}(c_{i-1}-c_{j-1})

然后就可以线性递推了。

最后答案就是：

E_{1\rightarrow n+1}=c_n

时间复杂度 O(n+m)。

最后注意取模中有减法，所以要加上模数。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=1e6,mo=998244353;

ll n,m,id,u,v,tot;

ll cnt_ae[N+5],ver[N+5],nxt[N+5],head[N+5],f[N+5],c[N+5];

void add(ll u,ll v) {
    ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    id=read();n=read();m=read();

    for(ll i=1;i<=m;i++) {
        u=read();v=read();
        add(u,v);cnt_ae[u]++;
    }

    for(ll i=1;i<=n;i++) {
        f[i]=(cnt_ae[i]+1)%mo;
        for(ll j=head[i];j;j=nxt[j]) {
            f[i]=(f[i]+(c[i-1]-c[ver[j]-1])%mo+mo)%mo;
        }
        c[i]=(c[i-1]+f[i])%mo;
    }

    write(c[n]);

    return 0;
}