No.3213 depth max K
タグ : / 解いたユーザー数 76
作問者 :
Cafe1942
/ テスター :
yuusaan
👑 
loop0919
lif4635
問題文
長さ $2N$ の正しい括弧列のうち、「括弧列のもっとも深い所の深さ」がちょうど $K$ であるようなものは何通りありますか。
正しい括弧列とは?
正しい括弧列とは、以下のいずれかの条件を満たす空でない文字列です。()- 正しい括弧列 $A$ が存在し、
($,A,$)をこの順に結合した文字列 - 正しい括弧列 $A,B$ が存在し、 $A,B$ をこの順に結合した文字列
ただし、答えが非常に大きくなる可能性があるため、 $998244353$ で割った余りを回答してください。
ここで、「括弧列のもっとも深い所の深さ」とは、正しい括弧列を次の手順にしたがって操作したときに定義される量です。正しくない括弧列についてはここでは考えません。
変数 $\text{depth},\text{ans}$ を用意して、 $\text{depth} = 0,\text{ans} = 0$ と初期化する。
次の操作を、括弧列の先頭から末尾まで順に1文字ずつ行う。
- いま注目している文字が
(であれば、変数 $\text{depth}$ を $1$ 増やす。そうでなく、いま注目している文字が)であれば、変数 $\text{depth}$ を $1$ 減らす。 - もし、$\text{ans}$ が $\text{depth}$ よりも小さいなら、$\text{ans}$ に $\text{depth}$ を代入する。
- いま注目している文字が
このときの $\text{ans}$ を「括弧列のもっとも深い所の深さ」と定義する。
たとえば、(())()なら「括弧列のもっとも深い所の深さ」は $2$ 、((()(())))なら「括弧列のもっとも深い所の深さ」は $4$ です。
制約
- $1 \leq N \leq 5000 $
- $1 \leq K \leq N $
- 与えられる入力はすべて整数
入力
$N$ $K$
出力
答えを $998244353$ で割った余りを出力してください。
サンプル
サンプル1
入力
3 2
出力
3
(())(),()(()),(()())の $3$ 通りです。
サンプル2
入力
1 1
出力
1
()の $1$ 通りです。
サンプル3
入力
21 10
出力
87633350
真の値は $1085877703$ ですが、 $998244353$ で割った余り $87633350$ を出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。