← 返回题单

题单练习概率与期望DP

← 上一题下一题 →

A7130 | $深海少女与胖头鱼$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

题目背景 Amazing John 做了一个梦，梦到他上上辈子是个少女。 她跳入了 OI ~~炉石~~ 的海洋，成为了 深海少女 ，维护着海洋的秩序。 某一天，海洋遭到了胖头鱼群的入侵。为了维护深海的安全，Amazing John 带着大佬们与胖头鱼们战斗了 $9$ 天 $9$ 夜，但是鱼的数量并没减少。 题目描述 经过漫长的战斗，Amazing John 发现了战胜胖头鱼的方法： 总共有 $n$ 条带 「圣盾」的「胖头鱼」和 $m$ 条不带圣盾的胖头鱼，每次等概率对一条存活的胖头鱼造成「剧毒」伤害。 现在 Amazing John 想知道，期望造成多少次伤害可以杀死全部胖头鱼？ 答案对 $998244353$ 取模。 「圣盾」：当拥有圣盾的胖头鱼受到伤害时，免疫这条鱼所受到的本次伤害。免疫伤害后，圣盾被破坏。 「胖头鱼」：在一条胖头鱼的圣盾被破坏后，给予其他所有没有死亡且没有圣盾的胖头鱼圣盾。 「剧毒」：立即杀死没有圣盾的胖头鱼。

输入格式

输入共一行，包含两个非负整数 $n,m$，表示有 $n$ 条带圣盾的胖头鱼，有 $m$ 条不带圣盾的胖头鱼。

输出格式

输出共一行，一个非负整数 $s$，表示期望造成伤害次数对 $998244353$ 取模的值。 具体的，答案必然可以表示成 $\frac{p}{q}(p,q\in \mathbb{N},q\neq 0)$ 的形式，而你需要输出 $p×q^{-1}$ 在模 $998244353$ 意义下的值。

输入输出样例

输入 #1

2 1

输出 #1

输入 #2

10 10

输出 #2

499122389

输入 #3

10 0

输出 #3

输入 #4

2 0

输出 #4

本题共有 $20$ 个数据点，数据点从 $1$ 到 $20$ 编号。对于一个子任务，只有通过其中所有数据点才能获得该子任务的分数。 子任务数据点数据范围分数$1$$1\sim3$$n,m \le 5 \times 10^3$$15$$2$$4\sim5$$n \le 10^6$，$m=0$$10$$3$$6\sim10$$n,m \le 10^6$$25$$4$$11\sim14$$n \le 10^{14}$，$m=0$$20$$5$$15\sim20$$n \le 10^{14}$，$m\le 10^6$$30$ 答案的形式 $\frac{p}{q}$ 必然满足 $(p,q\in \mathbb{N},998244353\nmid q)$

C++ 编辑器

输入

输出