ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 Y: 括号序列

内存限制：256 MB 时间限制：1 S
题面：传统 评测方式：文本比较 上传者：
提交：7 通过：7
返回比赛提交提交记录

题目描述

给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。

例如，对于括号序列 `((()`，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：`()()()` 、`()(())`、`(())()`、`(()())` 和 `((()))`。
原题链接：P8745 [蓝桥杯 2021 省 AB] 括号序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

输入格式

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

输出格式

输出一个整数表示答案，答案可能很大，请输出答案除以 $1000000007$（即 $10^{9}+7$）的余数。

输入样例 复制 

((()

输出样例 复制 

5

数据范围与提示

对于 $40 \%$ 的评测用例，$|s| \leq 200$。

对于所有评测用例，$1 \leq|s| \leq 5000$。 

蓝桥杯 2021 第一轮省赛 A 组 I 题（B 组 J 题）。

分类标签