問題一覧 > 通常問題

No.3043 Counting Bracket Sequences

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 55
作問者 : nauclhlt / テスター : eiram Blue_S naniwazu
お気に入りにしたユーザー ProblemId : 11808 / 自分の提出
問題文最終更新日: 2025-02-09 01:40:52
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 458 (順位表) の他の問題:

Story

eiram loves balanced bracket sequences, but he considers ()()() to be less valuable than ((())).
How much value does eiram feel in the balanced bracket sequences of a given length?

Problem Statement

A string $X$ is called a balanced bracket sequence if it satisfies the following. (This is the same as the definition commonly seen in competitive programming problem statements.)

  • $X$ can be made into the empty string by repeating, 0 or more times, the operation of deleting a () contained in $X$ as a contiguous substring.

For example, ()(()) and ()()()() are balanced bracket sequences, but ))(( and )()()( are not balanced bracket sequences.

For a balanced bracket sequence $T$, let $f(T)$ be the value of $x$ after performing the following procedure.

  • Initially, let $S$ be the empty set and $x=0$. For $i=1, 2, \cdots, N$ in this order, do the following:
    • If $T_i=$(, add $i$ to $S$.
    • If $T_i=$), remove from $S$ the $j(1\leq j\lt i)$ such that "the string extracted from the open interval $(j, i)$ of $T$ is a balanced bracket sequence", and then add the number of elements of $S$ to $x$.

    • For example, $f($()(())$)=1, f($()()()$)=0$.

    Given a positive integer $N$, find the sum of $f(S)$ over all strings possible as a balanced bracket sequence $S$ of length $N$.
    Since the answer can be very large, find the remainder when divided by $998244353$.

    Notation for strings For a string $A$, where $|A|$ is the length of $A$, $A_i(1\leq i\leq |A|)$ denotes the $i$-th character of $A$.

    Input

    $N$
    • $1\leq N\leq 2000$
    • All inputs are integers.

    Output

    Let $r$ be the remainder when the sum of $f(S)$ is divided by $998244353$. Print it on 1 line in the following format.

    $r$

    Print a newline at the end.

    Sample

    Sample 1
    Input
    2
    Output
    0

    The only balanced bracket sequence of length 2 is (). Since $f($()$)=0$, print 0.

    Sample 2
    Input
    4
    Output
    1

    The balanced bracket sequences of length 4 are the 2 strings (()) and ()(). Since $f($(())$)=1$, $f($()()$)=0$, print 1.

    Sample 3
    Input
    11
    Output
    0

    There is no balanced bracket sequence of length 11.

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