問題一覧 > 通常問題

No.2031 Colored Brackets

レベル : / AI推定難易度 : 1325 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 111
作問者 : Shirotsume / テスター : ygussany とりゐ
お気に入りにしたユーザー ProblemId : 8156 / 自分の提出
問題文最終更新日: 2022-08-05 19:51:13
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 355 (順位表) の他の問題:

Problem Statement

A string satisfying any of the following conditions is defined as a correct bracket sequence.

  • The empty string
  • 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 non-empty correct bracket sequences $A, B$

You are given a correct bracket sequence $S$ of length $N$. There are $2^N$ ways in total to paint each character of $S$ either red or blue. How many of them satisfy the following condition? Find the answer modulo $998244353$.

  • Let $X$ be the string formed by taking only the characters painted red from $S$ without changing their order, and let $Y$ be the string formed by taking only the characters painted blue without changing their order. Both $X, Y$ are correct bracket sequences.

Constraints

  • $2 \leq N \leq 3000$
  • $N$ is an integer.
  • $S$ is a correct bracket sequence.
  • Input

    The input is given from standard input in the following format.

    $N$
    $S$
    

    Output

    Output the number of valid ways to paint, modulo $998244353$.

    Sample

    Sample 1
    Input
    4
    (())
    Output
    6

    For clarity, characters painted red are represented by () and characters painted blue by []. The following $6$ ways of painting satisfy the condition.

    • (())
    • [[]]
    • ([])
    • [()]
    • [(])
    • ([)]
    Sample 2
    Input
    4
    ()()
    Output
    4

    The following $4$ ways satisfy the condition.

    • ()()
    • [][]
    • ()[]
    • []()
    Sample 3
    Input
    12
    (()())()(())
    Output
    216
    Sample 4
    Input
    50
    ((((((((((((((((((((((((()))))))))))))))))))))))))
    Output
    927528656

    Output the answer modulo $998244353$.

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