No.2031 Colored Brackets
タグ : / 解いたユーザー数 111
作問者 :
とりゐ
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
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もしくは右上の雲マークをクリックしてアカウントを作成してください。