問題一覧 > 通常問題

No.2031 Colored Brackets

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 105
作問者 : ShirotsumeShirotsume / テスター : ygussanyygussany とりゐとりゐ
2 ProblemId : 8156 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-05 19:51:13

問題文

以下の条件のいずれかを満たす文字列を 正しい括弧列 と定義します。

  • 空文字列
  • ある正しい括弧列 $A$ が存在して、 ($,A,$ ) をこの順に連結した文字列
  • ある空でない正しい括弧列 $A, B$ が存在して、 $A,B$ をこの順に連結した文字列

長さ $N$ の正しい括弧列 $S$ が与えられます。$S$ の各文字を赤と青に塗り分ける方法は全部で $2^N$ 通りありますが、そのうち以下の条件を満たすものは何通りあるでしょうか？この答えを $998244353$ で割ったあまりを求めてください。

  • $S$ から赤く塗られた文字のみを順番を変えずに取り出してできる文字列を $X$ 、青く塗られた文字のみを順番を変えずに取り出してできる文字列を $Y$ とする。 $X, Y$ はともに正しい括弧列である。

制約

  • $2 \leq N \leq 3000$
  • $N$ は整数
  • $S$ は正しい括弧列である。

    • 入力

    入力は標準入力から以下の形式で与えられる。

    $N$
$S$

    出力

    条件を満たす塗り分け方の個数を $998244353$ で割ったあまりを出力せよ。

    サンプル

    サンプル1
    入力
    4
(())
    出力
    6

    わかりやすくするため、赤く塗られたものを ()、青く塗られたものを [] で表します。以下の $6$ 種類の塗り方が条件を満たします。

    • (())
    • [[]]
    • ([])
    • [()]
    • [(])
    • ([)]
    サンプル2
    入力
    4
()()
    出力
    4

    以下の $4$ 種類が条件を満たします。

    • ()()
    • [][]
    • ()[]
    • []()
    サンプル3
    入力
    12
(()())()(())
    出力
    216
    サンプル4
    入力
    50
((((((((((((((((((((((((()))))))))))))))))))))))))
    出力
    927528656

    $998244353$ で割ったあまりを出力してください。

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