← 返回题目列表

AtCoder · arc185_d

D. 树上的随机游走

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

有一棵树 N \times M + 1 顶点编号 0, 1, \dots, N \times M。的 i第边缘 (1 \leq i \leq N \times M) 连接顶点 i 和 \max(i - N, 0).
顶点 0 已涂漆。其他顶点未绘制。
高桥位于顶点 0。只要存在未绘制的顶点,他就会执行以下操作:

  • 他均匀地随机选择与当前顶点相邻的顶点之一(所有选择都是独立的)并移动到该顶点。然后,如果他所在的顶点未绘制,他就会绘制它。

求他执行该操作的预期次数,取模 998244353.

期望值模是多少 998244353?

可以证明,所求的期望值总是有理数。在这个问题的约束下,当该值表示为不可约分数时 \frac{P}{Q},还可以证明 Q \not\equiv 0 \pmod{998244353}。那么,唯一存在一个整数 R 这样 R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353。报告此事 R.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • N 和 M 是整数。

输入

输入由标准输入按以下格式给出:

N M

输出

打印他执行该操作的预期次数,取模 998244353.


示例输入 1

2 2

示例输出 1

20

例如,Takahashi 的行为如下。

  • 移动到顶点 1 并绘制它。该动作是按概率选择的 \frac{1}{2}.
  • 移动到顶点 0。该动作是按概率选择的 \frac{1}{2}.
  • 移动到顶点 1。该动作是按概率选择的 \frac{1}{2}.
  • 移动到顶点 3 并绘制它。该动作是按概率选择的 \frac{1}{2}.
  • 移动到顶点 1。该动作是按概率选择的 1.
  • 移动到顶点 0。该动作是按概率选择的 \frac{1}{2}.
  • 移动到顶点 2 并绘制它。该动作是按概率选择的 \frac{1}{2}.
  • 移动到顶点 4 并绘制它。该动作是按概率选择的 \frac{1}{2}.

他有这种行为的概率 \frac{1}{128},在这种情况下操作数为 8。预期操作次数为 20.


示例输入 2

123456 185185

示例输出 2

69292914