[Cnoi2020]线性生物

期望入门题。但是我不会做。

考虑设\(E_{x\to{x+1}}\)为\(x\)到\(x+1\)点的期望步数。

则\(ans = \sum_{i = 0}^{n} E_{x\to{x+1}}\)

知\(E_{y\to{x+1}} = \sum_{i = y}^{x}E_{i\to{i + 1}}\)

\(E_{x\to{x+1}} = \frac{1}{son + 1} + \frac{1}{son + 1}\sum_{(x,y)\ in\ {Son}}(E_{y\to{x+1}} + 1)\)

设\(E_{x\to{x+1}} = f_x\),\(sum_x = \sum_i^xf_i\)

\(f_x = (son + 1) + \sum_{(x,y)\ in\ Son}sum_{x-1} - sum_{y - 1}\)

// Problem: P6835 [Cnoi2020]线形生物

// Contest: Luogu

// URL: https://www.luogu.com.cn/problem/P6835

// Memory Limit: 128 MB

// Time Limit: 1000 ms

//

// Powered by CP Editor (https://cpeditor.org)

#include<iostream>

#include<cstdio>

#define ll long long

#define mod 998244353

#define N 1000005

int head[N],cnt;

struct P{

	int to,next;

}e[N << 1];

inline void add(int x,int y){

	e[++cnt].to = y;

	e[cnt].next = head[x];

	head[x] = cnt;

}

ll n,m,k,out[N];

ll f[N],sum[N];

int main(){

	scanf("%lld%lld%lld",&k,&n,&m);

	for(int i = 1;i <= m;++i){

		ll l,r;

		scanf("%lld%lld",&l,&r);

		add(l,r);

		out[l]++;

	}

	for(int i = 1;i <= n;++i){

		f[i] = (out[i] + 1);

		for(int j = head[i];j;j = e[j].next){

			int v = e[j].to;

			f[i] = (f[i] + (sum[i - 1] - sum[v - 1]) % mod + mod) % mod;

		}

		sum[i] = (sum[i - 1] + f[i]) % mod;

	}

	std::cout<<sum[n] % mod<<std::endl;

	return 0;

}

巴特西

[Cnoi2020]线性生物

最新文章

热门文章