I - Free will, but limited
Darjeeling
2
s
1024
MB
550
点
問題文
無限に広がる2次元平面の座標$(X, Y)$に駒があります。座標$(0, 0)$には穴があり、駒はこのマスに移動すると平面上から消えます。駒が平面上にある限り、以下の操作を繰り返します。
- 上下左右いずれかの方向に1だけ動かす。
- その後、駒が平面上にあれば、上下左右いずれかに等確率で1だけランダムに動く。
駒が平面上から消えるまでに動く回数を最小化するように操作した時の、駒が動く回数の期待値を $\bmod\ 998244353$ で求めてください。
期待値 $\bmod\ 998244353$ とは？
求める期待値は必ず有理数になることが証明できます。
また、この問題の制約のもとでは、その値を既約分数 $\frac{P}{Q}$ で表したとき、
$Q \not\equiv 0\ \pmod{998244353}$ となることも証明できます。
よって、 $R \times Q \equiv P\ \pmod{998244353}, 0 \leq R <998244353$ を満たす
整数 $R$ が一意に定まります。この $R$ を答えてください。
制約
- $1 \le X \le 998244352$
- $X \le Y \le X + 3$
- 与えられる値はすべて整数
入力
$X$ $Y$
出力
操作回数の期待値を $\bmod\ 998244353$ で出力してください。
入力例 1
1 1
出力例 1
8
駒が動く回数を最小化するための操作の一例は、以下の通りです。
- 最初、駒は$(1,1)$にある。
- 駒を左に動かし、$(0,1)$に移動する。
- 駒が上に動き、$(0,2)$に移動される。
- 駒を下に動かし、$(0,1)$に移動する。
- 駒が下に動き、$(0,0)$に移動する。
- 駒が$(0,0)$に置かれたため、駒が平面上から消える。
この例では、駒が動いた回数は$4$回です。
なお、駒が動く回数を最小化する時の、駒が動く回数の期待値は$8$と求めることができます。
入力例 2
1 2
出力例 2
5
入力例 3
990000000 990000003
出力例 3
413061344