HBC222905[NOIP2003]加分二叉树,动态规划,区间dp黑暗洞窟丶明亮之网题解

初见你算法基础篇 2023-11-19 18:29:02 56 0

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

更好的阅读体验：链接：https://pan.baidu.com/s/1o4smgWB19XF7_N_0SJ1R9Q，提取码：dkq4 ，题目背景largetextsf{题目背景}题目背景黑谷山女是生活在洞穴里的蜘蛛妖怪，尽管如此，作为拥有蜘蛛能力的土蜘蛛，山女常常通过建筑巨大的蜘蛛网完成一些土木工程上的工作，是一个非常忙碌的打工人，当然，山女除了会建造

更好的阅读体验：链接：https://pan.baidu.com/s/1o4smgWB19XF7_N_0SJ1R9Q ，提取码：dkq4 。题目背景largetextsf{题目背景}题目背景黑谷山女是生活在洞穴里的蜘蛛妖怪。尽管如此，作为拥有蜘蛛能力的土蜘蛛，山女常常通过建筑巨大的蜘蛛网完成一些土木工程上的工作，是一个非常忙碌的打工人。当然，山女除了会建造蜘蛛网，同样会拆除蜘蛛网。对于形如脚手架一般的蜘蛛网，在建筑完工后当然就要拆除了。但在拆除过程中，山女遇到了一点小麻烦。不同的蜘蛛丝会在一些地点打结，这些网结直接影响了拆除与之相连的边所花费的时间。然而山女太忙碌了来不及计算出一个最优方案，只能每次等概率地选取一条剩下的边进行拆除。山女选择了一些边作为采样点，来估算拆除整张网的总时间。但由于网太复杂，所花费的时间难以计算，因此她来求助了。题目描述largetextsf{题目描述}题目描述整张蜘蛛网可以认为是一个 nmathit nn 个节点、 mmathit mm 条边的无向图，每个节点的粘度就是与它相连的边的数目。山女每次随机选取一条剩余的边进行拆除，花费的时间就是两端节点的粘度之和。当拆除这条边后，两端节点的粘度分别会下降。我们计删除第 imathit ii 条边花费的时间为 TiT_iTi 。此外，蜘蛛网上有 kmathit kk 条特殊的边，分别为 x1,x2⋯xkx_1,x_2cdots x_kx1,x2⋯xk 。山女想知道删除这些边时花费时间的和的期望。即： E(∑i=1kTxi)Eleft(sum_{i=1}^k T_{x_i}right)E(∑i=1kTxi) 由于这个结果很大，山女只要你将结果对 998244353mathrm{998244353}998244353 (一个质数，等于 7×17×223+17times 17times 2^{23}+17×17×223+1 ) 取模就行了。