2607 問題 B: 藍橋杯2021年第十二屆省賽真題-括號序列
時間限制: 1s
內(nèi)存限制: 128MB 提交: 1581 解決: 201
題目描述
給定一個括號序列，要求盡可能少地添加若干括號使得括號序列變得合法，當(dāng)添加完成后，會產(chǎn)生不同的添加結(jié)果，請問有多少種本質(zhì)不同的添加結(jié)果。兩個結(jié)果是本質(zhì)不同的是指存在某個位置一個結(jié)果是左括號，而另一個是右括號。
例如，對于括號序列 ((()，只需要添加兩個括號就能讓其合法，有以下幾種不同的添加結(jié)果：()()()、()(())、(())()、(()()) 和 ((()))。
輸入
輸入一行包含一個字符串 s，表示給定的括號序列，序列中只有左括號和
右括號。
輸出
輸出一個整數(shù)表示答案，答案可能很大，請輸出答案除以 1000000007 (即109 + 7) 的余數(shù)。
提示
【評測用例規(guī)模與約定】
對于 40% 的評測用例，|s| ≤ 200。
對于所有評測用例，1 ≤ |s| ≤ 5000。