g545: 收納盒 (Storage Box)
Tags :
Accepted rate : 20人/27人 ( 74% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-11-21 22:32

Content

給定一個字串序列S,將所有的 '?' 替換成 '[' 或 ']',請計算出有幾種組合符合括號序列

範例:

S = "?]??" -> [][] 一種

S = "??????" -> [][][], [[]][], [[][]], [][[]], [[[]]] 五種

Input

第一行輸入1個正偶數N (2 ≤ N ≤ 2,000)

第二行包含1個長度為N的字串S,其中S只包含'[', ']', '?' 3種字元

Output

輸出所有符合括號序列的數量 mod $10^9 + 7$

Sample Input #1
4
[??]
Sample Output #1
2
Sample Input #2
6
?]]?]?
Sample Output #2
0
Sample Input #3
30
??????????????????????????????
Sample Output #3
9694845
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1M
不公開 測資點#2 (10%): 1.0s , <1M
不公開 測資點#3 (10%): 1.0s , <1M
不公開 測資點#4 (10%): 1.0s , <1M
不公開 測資點#5 (10%): 1.0s , <1M
不公開 測資點#6 (10%): 1.0s , <1M
不公開 測資點#7 (10%): 1.0s , <1M
不公開 測資點#8 (10%): 1.0s , <1M
不公開 測資點#9 (10%): 1.0s , <1M
Hint :

此題目測資分成三組,每組測資有多筆測試資料,需答對該組所有測試資料才能獲得該組分數,各組詳細限制如下。
第一組 (20分):S中不包含 '?' 字元。

第二組 (20分):S中 '?' 字元的個數 ≤ 10。

第三組 (60分):依題敘。

Tags:
出處:
TOI練習賽202110潛力組 [管理者:
fire5386 (fffelix)
]


ID User Problem Subject Hit Post Date
28019
r1cky (木叢欉木叢)
g545
解法提示
112 2021-11-10 13:59