No.2877 Gunegune Hyperion
タグ : / 解いたユーザー数 20
作問者 :
寝癖
/ テスター :
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もしくは右上の雲マークをクリックしてアカウントを作成してください。