問題一覧 > 通常問題

No.2877 Gunegune Hyperion

レベル : / AI推定難易度 : 2150 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : 寝癖 / テスター : yuusaan 👑 seekworser
お気に入りにしたユーザー ProblemId : 11208 / 自分の提出
問題文最終更新日: 2024-09-04 17:23:13
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 444 (順位表) の他の問題:

Problem Statement

* The TL for this problem is set strictly, so using a fast language is recommended.
* Also, this problem has the same setting as E: Gunegune Tree; only the value to be found differs.

Neguse-kun has bought the seed of a mysterious plant. He is going to grow it at his home starting today.

Taking today as day $0$, the plant grows according to the following rules as each $1$ day passes.

  • On day $0$, the tip of the plant is at the origin $(0,0)$ of the $2$-dimensional plane.
  • Let $(x,y)$ be the coordinates of the tip of the plant on day $i\ (\ge0)$. Then the coordinates of the tip of the plant on day $i+1$ are one of $(x+1,y),(x+1,y+1),(x,y+1),(x-1,y+1),(x-1,y)$. That is, it grows in one of the directions right, upper right, up, upper left, or left.
  • Let $P_i,P_{i+1},P_{i+2}$ be the positions of the tip of the plant on days $i,i+1,i+2$. Then $\angle P_iP_{i+1}P_{i+2}>90^\circ$ is satisfied. That is, it never bends at an acute or right angle.
  • The direction of growth is chosen independently and uniformly at random from all possible directions.

Neguse-kun is troubled by the low ceiling of his home and is very concerned about how tall this plant will grow.

This time, find the probability that the height of the plant (that is, the $y$-coordinate of the tip) on day $N$ after starting to grow it is at least $H$, modulo ${\rm mod}\ 998244353$.

What is a probability ${\rm mod}\ 998244353$?

It can be proved that the desired probability is always a rational number. Moreover, under the constraints of this problem, when the desired probability is expressed as an irreducible fraction $\frac{p}{q}$, it is guaranteed that $q$ is not divisible by $998244353$. In this case, there exists a unique $0\le r < 998244353$ satisfying $p=qr\ ({\rm mod}\ 998244353)$, so output this $r$.

Input

$N$ $H$
  • $1\le H \le N\le 2\times 10^5$
  • All inputs are integers.

Output

Output on one line the probability, ${\rm mod}\ 998244353$, that the height of the plant on day $N$ is at least $H$.

Sample

Sample 1
Input
2 1
Output
399297742

The height is less than $1$ when the growth on day $1$ and day $2$ is

  • (right, right)
  • (left, left)

and each of these occurs with probability $\frac15\times\frac12=\frac{1}{10}$. Therefore, the desired probability is $1-\frac{2}{10}=\frac45$.

Sample 2
Input
6 4
Output
425178151
Sample 3
Input
314 15
Output
532649373

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。