No.2872 Depth of the Parentheses
タグ : / 解いたユーザー数 90
作問者 :
寝癖
/ テスター :
yuusaan
👑 
seekworser
問題文
寝癖くんは、表が出る確率が $x\%$ で、裏が出る確率が $(100-x)\%$ のコインと空文字 $S$ を持っています。
いま、以下の試行を $2K$ 回繰り返すことを考えます。
コインを投げ、
- 表が出たら $S$ の末尾に
(を追加する。 - 裏が出たら $S$ の末尾に
)を追加する。
このようにして得られる長さ $2K$ の 括弧列 $S$ について、その深さの期待値を ${\rm mod}\ 998244353$ で求めてください。
ただし、括弧列 $S$ の深さとは、以下で定められる値のことをいいます。
$S$ の先頭 $i$ 文字からなる文字列 $T_i$ に対して、$T_i$ の末尾に ) を追加して正しい括弧列にするために必要な最小の ) の数を $D_i$ とするとき
- $S$ が正しい括弧列ならば $\displaystyle\max_{1\le i\le 2K}D_i$.
- そうでないならば $0$.
(())() の深さは $2$、() の深さは $1$、((()))(( の深さは $0$（正しい括弧列でない）となります。
期待値 ${\rm mod}\ 998244353$ とは
求める期待値は必ず有理数になることが証明できます。また、この問題の制約下では、求める期待値を既約分数 $\frac{p}{q}$ で表したときに、$q$ が $998244353$ で割り切れないことが保証されます。このとき、$p=qr\ ({\rm mod}\ 998244353)$ を満たす $0\le r < 998244353$ がただ一つ存在するので、$r$ を出力してください。
正しい括弧列とは
正しい括弧列とは、以下のいずれかを満たす空でない文字列のことをいいます。
()- ある正しい括弧列 $S,T$ が存在し、$S,T$ をこの順に連結した文字列
- ある正しい括弧列 $S$が存在し、
(,$S$,)をこの順に連結した文字列
入力
入力は以下の形式で標準入力から与えられます。$x\ K$
- $0\le x\le 100$
- $1\le K \le 10$
- 入力はすべて整数
この問題には高難易度の制約が、AC判定とは関係のないevilケースとして用意されています。余力のある方はぜひ挑戦してみてください。evilケースの制約は以下のようになっています。
evilケースの制約
- $0\le x\le 100$
- $1\le K \le 10000$
- 入力はすべて整数
出力
答えを1行で出力してください。
サンプル
サンプル1
入力
50 2
出力
811073537
得られる括弧列とその確率は以下のようになります。
- 確率 $\frac{1}{16}$ で
(()) - 確率 $\frac{1}{16}$ で
()() - 確率 $\frac{7}{8}$ で正しい括弧列でない
サンプル2
入力
100 5
出力
0
得られた括弧列が正しい括弧列となる確率は $0$ です。
サンプル3
入力
31 4
出力
414773523
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。