A7130. 深海少女与胖头鱼
编程题
普及+/提高
知识点
题目描述
## 题目背景
Amazing John 做了一个梦,梦到他上上辈子是个少女。
她跳入了 OI ~~炉石~~ 的海洋,成为了[深海少女](https://music.163.com/#/song?id=22677451),维护着海洋的秩序。
某一天,海洋遭到了胖头鱼群的入侵。为了维护深海的安全,Amazing John 带着大佬们与胖头鱼们战斗了 $9$ 天 $9$ 夜,但是鱼的数量并没减少。
## 题目描述
经过漫长的战斗,Amazing John 发现了战胜胖头鱼的方法:
总共有 $n$ 条带 「圣盾」的「胖头鱼」和 $m$ 条不带圣盾的胖头鱼,每次等概率对一条存活的胖头鱼造成「剧毒」伤害。
现在 Amazing John 想知道,期望造成多少次伤害可以杀死全部胖头鱼?
答案对 $998244353$ 取模。
「圣盾」:当拥有圣盾的胖头鱼受到伤害时,免疫这条鱼所受到的本次伤害。免疫伤害后,圣盾被破坏。
「胖头鱼」:在一条胖头鱼的圣盾被破坏后,给予其他所有没有死亡且没有圣盾的胖头鱼圣盾。
「剧毒」:立即杀死没有圣盾的胖头鱼。
Amazing John 做了一个梦,梦到他上上辈子是个少女。
她跳入了 OI ~~炉石~~ 的海洋,成为了[深海少女](https://music.163.com/#/song?id=22677451),维护着海洋的秩序。
某一天,海洋遭到了胖头鱼群的入侵。为了维护深海的安全,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$ 意义下的值。
具体的,答案必然可以表示成 $\frac{p}{q}(p,q\in \mathbb{N},q\neq 0)$ 的形式,而你需要输出 $p×q^{-1}$ 在模 $998244353$ 意义下的值。
输入输出样例
输入 #1
2 1
输出 #1
8
输入 #2
10 10
输出 #2
499122389
输入 #3
10 0
输出 #3
65
输入 #4
2 0
输出 #4
5
说明/提示
本题共有 $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)$
| 子任务 | 数据点 | 数据范围 | 分数 |
| ------ | ---------- | ---------------------------- | ---- |
| $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)$