問題一覧 > 通常問題

No.2877 Gunegune Hyperion

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : 寝癖寝癖 / テスター : yuusaanyuusaan 👑 seekworserseekworser
0 ProblemId : 11208 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-09-04 17:23:13

問題文

※この問題の TL は厳しめに設定されているため、 高速な言語の使用を推奨します。
※また、E: Gunegune Tree と問題の設定は同一であり、求めるべき値のみが異なります。

寝癖くんは不思議な植物の種を買ってきました。今日から自分の家で育てようとしています。

今日を $0$ 日目として、この植物は $1$ 日経つごとに、次のルールで成長していきます。

  • $0$ 日目、植物の先端は $2$ 次元平面上の原点 $(0,0)$ にある。
  • $i\ (\ge0)$ 日目の植物の先端の座標を $(x,y)$ としたとき、$i+1$ 日目の植物の先端の座標は $(x+1,y),(x+1,y+1),(x,y+1),(x-1,y+1),(x-1,y)$ のいずれかである。すなわち、右、右上、上、左上、左のいずれかの方向に伸びる。
  • $i,i+1,i+2$ 日目の植物の先端の位置を $P_i,P_{i+1},P_{i+2}$ とすると、$\angle P_iP_{i+1}P_{i+2}>90^\circ$ を満たす。すなわち鋭角や直角に折れ曲がることはない。
  • 伸びる方向は可能なすべての方向から等確率で独立に選ばれるとする。

寝癖くんは自分の家の天井の低さに悩まされており、この植物がどのくらいの高さまで伸びるのかをとても気にしています。

今度は育て始めてから $N$ 日目の植物の高さ(すなわち先端の $y$ 座標)が $H$ 以上となる確率 を ${\rm mod}\ 998244353$ で求めてください。

確率 ${\rm mod}\ 998244353$ とは

求める確率は必ず有理数になることが証明できます。また、この問題の制約下では、求める確率を既約分数 $\frac{p}{q}$ で表したときに、$q$ が $998244353$ で割り切れないことが保証されます。このとき、$p=qr\ ({\rm mod}\ 998244353)$ を満たす $0\le r < 998244353$ がただ一つ存在するので、$r$ を出力してください。

入力

$N$ $H$
  • $1\le H \le N\le 2\times 10^5$
  • 入力はすべて整数

出力

$N$ 日目の植物の高さが $H$ 以上となる確率 ${\rm mod}\ 998244353$ を一行で出力してください。

サンプル

サンプル1
入力
2 1
出力
399297742

高さが $1$ 未満となるのは、$1$ 日目と $2$ 日目の伸び方が

  • (右, 右)
  • (左, 左)

となるときであり、どちらも起こる確率は $\frac15\times\frac12=\frac{1}{10}$ です。よって求める確率は $1-\frac{2}{10}=\frac45$ となります。

サンプル2
入力
6 4
出力
425178151
サンプル3
入力
314 15
出力
532649373

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