Dotcpp  >  编程题库  >  蓝桥杯2021年第十二届省赛真题-括号序列
题目 2607:

蓝桥杯2021年第十二届省赛真题-括号序列

时间限制: 1Sec 内存限制: 128MB 提交: 798 解决: 118

题目描述

给定一个括号序列,要求尽可能少地添加若干括号使得括号序列变得合法,当添加完成后,会产生不同的添加结果,请问有多少种本质不同的添加结果。两个结果是本质不同的是指存在某个位置一个结果是左括号,而另一个是右括号。
例如,对于括号序列 (((),只需要添加两个括号就能让其合法,有以下几种不同的添加结果:()()()、()(())、(())()、(()()) 和 ((()))。

输入格式

输入一行包含一个字符串 s,表示给定的括号序列,序列中只有左括号和
右括号。

输出格式

输出一个整数表示答案,答案可能很大,请输出答案除以 1000000007 (即109 + 7) 的余数。

样例输入

((()

样例输出

5

提示

【评测用例规模与约定】
对于 40的评测用例,|s| ≤ 200
对于所有评测用例,≤ |s| ≤ 5000
标签

通过率

统 计

 提交 798
 正确 118
 格式错误 0
 答案错误 204
 时间超限 133
 内存超限 27
 输出超限 23
 运行错误 192
 编译错误 101