/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
頂点に 0, 1, \dots, N \times M の番号がついた N \times M + 1 頂点の木があります。i 本目の辺 (1 \leq i \leq N \times M) は頂点 i と頂点 \max(i - N, 0) を結ぶ辺です。
また、頂点 0 には色が塗られています。それ以外の頂点は色が塗られていません。
高橋君は頂点 0 にいます。高橋君は色が塗られていない頂点が存在する間、次の操作を行います。
- 自身がいる頂点に隣接する頂点の中から一様ランダムに頂点を 1 つ選んで、その頂点に移動する。(全ての選択は独立である。) そして、今いる頂点に色が塗られていなければ色を塗る。
操作を行う回数の期待値を \text{mod }998244353 で求めてください。
期待値 \text{mod }{998244353} の定義
求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \not \equiv 0 \pmod{998244353} となることも証明できます。このとき、R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 を満たす整数 R が一意に定まります。この R を答えてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- N, M は整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
操作を行う回数の期待値を \text{mod }998244353 で出力せよ。
入力例 1
2 2
出力例 1
20
高橋君は例えば以下のように行動します。
- 頂点 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
Score : 800 points
Problem Statement
There is a tree with N \times M + 1 vertices numbered 0, 1, \dots, N \times M. The i-th edge (1 \leq i \leq N \times M) connects vertices i and \max(i - N, 0).
Vertex 0 is painted. The other vertices are unpainted.
Takahashi is at vertex 0. As long as there exists an unpainted vertex, he performs the following operation:
- He chooses one of the vertices adjacent to his current vertex uniformly at random (all choices are independent) and moves to that vertex. Then, if the vertex he is on is unpainted, he paints it.
Find the expected number of times he performs the operation, modulo 998244353.
What is the expected value modulo 998244353?
It can be proved that the sought expected value is always rational. Under the constraints of this problem, when that value is expressed as an irreducible fraction \frac{P}{Q}, it can also be proved that Q \not\equiv 0 \pmod{998244353}. Then, there uniquely exists an integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353. Report this R.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- N and M are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Print the expected number of times he performs the operation, modulo 998244353.
Sample Input 1
2 2
Sample Output 1
20
For example, Takahashi could behave as follows.
- Moves to vertex 1 and paints it. This action is chosen with probability \frac{1}{2}.
- Moves to vertex 0. This action is chosen with probability \frac{1}{2}.
- Moves to vertex 1. This action is chosen with probability \frac{1}{2}.
- Moves to vertex 3 and paints it. This action is chosen with probability \frac{1}{2}.
- Moves to vertex 1. This action is chosen with probability 1.
- Moves to vertex 0. This action is chosen with probability \frac{1}{2}.
- Moves to vertex 2 and paints it. This action is chosen with probability \frac{1}{2}.
- Moves to vertex 4 and paints it. This action is chosen with probability \frac{1}{2}.
He behaves in this way with probability \frac{1}{128}, in which case the number of operations is 8. The expected number of operations is 20.
Sample Input 2
123456 185185
Sample Output 2
69292914