問題一覧 > 通常問題

No.3213 depth max K

レベル : / AI推定難易度 : 1450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 79
作問者 : Cafe1942 / テスター : yuusaan 👑 loop0919 lif4635
お気に入りにしたユーザー ProblemId : 12382 / 自分の提出
問題文最終更新日: 2025-07-25 21:11:26
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 475 (ゆるCafe) (順位表) の他の問題:

Problem Statement

Among the correct bracket sequences of length $2N$, how many have "the depth of the deepest part of the bracket sequence" equal to exactly $K$?

What is a correct bracket sequence? A correct bracket sequence is a non-empty string satisfying one of the following conditions.
  • ()
  • A string obtained by concatenating ( $,A,$ ) in this order, for some correct bracket sequence $A$
  • A string obtained by concatenating $A,B$ in this order, for some correct bracket sequences $A,B$

Since the answer can be very large, report it modulo $998244353$.

Here, "the depth of the deepest part of the bracket sequence" is a quantity defined by processing a correct bracket sequence according to the following procedure. Incorrect bracket sequences are not considered here.

  1. Prepare variables $\text{depth},\text{ans}$ and initialize them as $\text{depth} = 0,\text{ans} = 0$.

  2. Perform the following operation for each character in order, from the beginning to the end of the bracket sequence.

    • If the current character is (, increase the variable $\text{depth}$ by $1$. Otherwise, if the current character is ), decrease the variable $\text{depth}$ by $1$.
    • If $\text{ans}$ is less than $\text{depth}$, assign $\text{depth}$ to $\text{ans}$.

  3. The value of $\text{ans}$ at this point is defined as "the depth of the deepest part of the bracket sequence".

For example, "the depth of the deepest part of the bracket sequence" is $2$ for (())(), and $4$ for ((()(()))).

Constraints

  • $1 \leq N \leq 5000 $
  • $1 \leq K \leq N $
  • All values in the input are integers

Input

$N$ $K$

Output

Output the answer modulo $998244353$.

Sample

Sample 1
Input
3 2
Output
3

There are $3$ such sequences: (())(),()(()),(()()).

Sample 2
Input
1 1
Output
1

There is $1$ such sequence: ().

Sample 3
Input
21 10
Output
87633350

The true value is $1085877703$, but you should output $87633350$, its remainder modulo $998244353$.

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