問題一覧 > 通常問題

No.2872 Depth of the Parentheses

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 93
作問者 : 寝癖 / テスター : yuusaan 👑 seekworser
1 ProblemId : 10787 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-09-09 08:51:43

問題文

寝癖くんは、表が出る確率が x%x\% で、裏が出る確率が (100−x)%(100-x)\% のコインと空文字 SS を持っています。
いま、以下の試行を 2K2K 回繰り返すことを考えます。

コインを投げ、

  • 表が出たら SS の末尾に ( を追加する。
  • 裏が出たら SS の末尾に ) を追加する。

このようにして得られる長さ 2K2K の 括弧列 SS について、その深さの期待値を mod 998244353{\rm mod}\ 998244353 で求めてください。


ただし、括弧列 SS の深さとは、以下で定められる値のことをいいます。
SS の先頭 ii 文字からなる文字列 TiT_i に対して、TiT_i の末尾に ) を追加して正しい括弧列にするために必要な最小の ) の数を DiD_i とするとき

  • SS が正しい括弧列ならば max⁡1≤i≤2KDi\displaystyle\max_{1\le i\le 2K}D_i.
  • そうでないならば 00.
例えば、(())() の深さは 22、() の深さは 11、((()))(( の深さは 00（正しい括弧列でない）となります。

期待値 mod 998244353{\rm mod}\ 998244353 とは

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


正しい括弧列とは

正しい括弧列とは、以下のいずれかを満たす空でない文字列のことをいいます。

  • ()
  • ある正しい括弧列 S,TS,T が存在し、S,TS,T をこの順に連結した文字列
  • ある正しい括弧列 SSが存在し、(,SS,)をこの順に連結した文字列

入力

入力は以下の形式で標準入力から与えられます。 
x Kx\ K

  • 0≤x≤1000\le x\le 100
  • 1≤K≤101\le K \le 10
  • 入力はすべて整数

この問題には高難易度の制約が、AC判定とは関係のないevilケースとして用意されています。余力のある方はぜひ挑戦してみてください。evilケースの制約は以下のようになっています。

evilケースの制約
  • 0≤x≤1000\le x\le 100
  • 1≤K≤100001\le K \le 10000
  • 入力はすべて整数
なお、evilケースに挑戦しない場合、入力が通常制約を満たしていない場合に即座にプログラムを終了するようにしていただけると、ジャッジが早く終了します。

出力

答えを1行で出力してください。

サンプル

サンプル1
入力
50 2
出力
811073537

得られる括弧列とその確率は以下のようになります。

  • 確率 116\frac{1}{16} で (())
  • 確率 116\frac{1}{16} で ()()
  • 確率 78\frac{7}{8} で正しい括弧列でない
したがって、求める期待値は 116×2+116×1+78×0=316\frac{1}{16}\times2 + \frac{1}{16}\times 1 + \frac{7}{8}\times 0=\frac{3}{16} になります。

サンプル2
入力
100 5
出力
0

得られた括弧列が正しい括弧列となる確率は 00 です。

サンプル3
入力
31 4
出力
414773523

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