首页 > 其他分享 >P6835 [Cnoi2020]线形生物 题解

P6835 [Cnoi2020]线形生物 题解

时间:2022-09-26 20:00:42浏览次数:48  
标签:ch int 题解 sum Cnoi2020 dfrac1 MAXN P6835

通过这道题可以看出来 pz 根本不会期望

考虑期望线性性质,设 \(E_{x\to y}\) 表示从 \(x\) 走到 \(y\) 的期望步数,那么有 \(E_{1\to n+1}=\sum_{i=1}^nE_{i\to i+1}\),因此考虑计算 \(E_{i\to i+1}\),下记 \(f_i=E_{i\to i+1}\)。

设 \(d_i\) 表示 \(i\) 的返祖边边数,\(E\) 表示返祖边边集,\(sum_i=\sum_{p=1}^{i}f_p\)则有如下一系列转化:

\[E_{i\to i+1}=\dfrac1{d_x+1}\times1+\sum_{i\to u\in E}E_{u\to i+1} \]

\[E_{i\to i+1}=\dfrac1{d_x+1}\times1+\sum_{i\to u\in E}\sum_{p=u}^iE_{p\to p+1} \]

\[f_i=\dfrac1{d_x+1}+\sum_{i\to u\in E}(sum_i-sum_{u-1}) \]

下面这步将和式的 \(sum_i\) 提出,化简得到:

\[f_i=(d_x+1)+\sum_{i\to u\in E}(sum_{i-1}-sum_{u-1}) \]

维护前缀和即可。

Code:

/*
========= Plozia =========
	Author:Plozia
	Problem:P6835 [Cnoi2020]线形生物
	Date:2022/9/26
========= Plozia =========
*/

#include <bits/stdc++.h>
typedef long long LL;
using std::vector;

const int MAXN = 1e6 + 5;
const LL P = 998244353;
int n, m;
vector <int> Edge[MAXN];
LL f[MAXN], sum[MAXN];

int Read()
{
	int sum = 0, fh = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
	return sum * fh;
}

int main()
{
	Read(); n = Read(), m = Read();
	for (int i = 1; i <= m; ++i) { int u = Read(), v = Read(); Edge[u].push_back(v); }
	for (int i = 1; i <= n; ++i)
	{
		f[i] = Edge[i].size() + 1;
		for (int j = 0; j < Edge[i].size(); ++j)
			f[i] = ((f[i] + sum[i - 1] - sum[Edge[i][j] - 1]) % P + P) % P;
		sum[i] = (sum[i - 1] + f[i]) % P;
	}
	printf("%lld\n", sum[n]); return 0;
}

标签:ch,int,题解,sum,Cnoi2020,dfrac1,MAXN,P6835
From: https://www.cnblogs.com/Plozia/p/16732168.html

相关文章

  • P2569 [SCOI2010]股票交易 题解
    设\(f_{i,j}\)表示第1天至第\(i\)天,手上有\(j\)股股票时拥有的最多钱。考虑转移,首先就有\(f_{i,j}=-j\timesap_i\)即单纯买入,然后由转移方程定义有\(f_{i,j}=......
  • CF1155D 题解
    题目传送门题目分析说实话,第一眼这题以为是贪心...(事实上我看所有动态规划都像贪心)。然后接着发现贪心明显做不了,又看见最大子段和,很容易联想到\(\text{dp}\)。在设计......
  • 牛客题解 贝伦卡斯泰露
    链接:https://ac.nowcoder.com/acm/problem/14132来源:牛客网题解作者岛田小雅子序列的概念,需要区别于子串。本来以为是道DP题,看了下范围发现爆搜好像问题也不是很大......
  • 线段树学习笔记(基础&进阶)(一) | P3372 【模板】线段树 1 题解
    什么是线段树线段树是一棵二叉树,每个结点存储需维护的信息,一般用于处理区间最值、区间和等问题。线段树的用处对编号连续的一些点进行修改或者统计操作,修改和统计的复杂......
  • AGC028C Min Cost Cycle 题解
    考虑将\(\min(a_i,b_j)\)转化为任意选择\(a_i,b_j\),因为多出来的不合法状态答案一定不会变小。注意到一个合法的行走方案对于\(a_i,b_j\)的选择只有如下两种情况之一......
  • 题解【CF209C Trails and Glades】
    CF209CTrailsandGlades解题报告图论基础题。考虑一张无向联通图存在欧拉回路的条件是什么:每一个点的度数均为偶数。但这个条件的前提是连通图,那么我们可以考虑......
  • CSP2022 S2 练习二 题解
    ArbitrageA货币可以以\(x\)的汇率兑换B货币,就从A向B连一条权值为\(x\)的边,改一下\(Floyd\)即可。点击查看代码#include<iostream>#include<string>#i......
  • 牛客题解 水图
    链接:https://ac.nowcoder.com/acm/problem/18947来源:牛客网题解作者岛田小雅由题目中“\(n\)个点\(n-1\)条边的无向连通图”可得出这是一棵树。考虑使用树形DP。......
  • Xshell无法连接22端口问题解决办法汇总
    Xshell软件在进行远程连接过程中,会出现端口连接报错的问题,提示:“该IP地址的22端口连接失败”,这是怎么回事?今天小编就xshell软件无法连接22端口的问题,整理相关情形(ubuntu系......
  • iOS 开发者帐号 App转让/转移 及转移后的证书问题解答(多图慎入)
    原文:简书 帐号转移在此,将原帐号称为A帐号,新的帐号称为B帐号。现在需要将A帐号中的App转让到B帐号中。*登录A帐号,找到App如下图: 1.A账号APP点转让.jp......