首页 > 试题广场 >

小红的可爱括号串

[编程题]小红的可爱括号串
  • 热度指数：44 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\,\,\,\,\,\,\,\,\,\,小红有一个长度为 n 的括号串，仅包含左括号和右括号。如果一个括号串长度为偶数，并且左半部分都是左括号，右半部分都是右括号，左括号的数量和右括号的数量相等，那么这个括号串就是可爱的括号串。
\,\,\,\,\,\,\,\,\,\,现在小红想知道给定的括号串中有多少个子序列组成的括号串是可爱的。

\,\,\,\,\,\,\,\,\,如果字符串 t 可以通过删除字符串 s 中的若干（可能为零或全部）元素得到，则字符串 t 是字符串 s 的子序列。

输入描述:
\,\,\,\,\,\,\,\,\,\,第一行输入一个整数 n\ (2 \leq n \leq 10^5) 表示括号串的长度。
\,\,\,\,\,\,\,\,\,\,第二行输入一个长度为 n ，且仅包含左右括号的括号串。


输出描述:
\,\,\,\,\,\,\,\,\,\,输出一个整数，表示给定的括号串中有多少个子序列组成的括号串是可爱的。由于答案可能很大，请将答案对 (10^9+7) 取模后输出。
示例1

输入

4
(())

输出

5

说明

\,\,\,\,\,\,\,\,\,\,存在 4 个长度为 2 的子序列是可爱括号串，存在 1 个长度为 4 的子序列是可爱括号串。
示例2

输入

10
()((())()(

输出

36
示例3

输入

4
))((

输出

0
算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-12 14:36:53
题目链接 小红的可爱括号串 题目描述 一个括号串被称为“可爱的”，当且仅当它满足以下所有条件： 长度为偶数。 左半部分全部是 (。 右半部分全部是 )。 左右括号数量相等。 例如 (()) 是可爱的，因为它由 ( 和 ) 组成，长度为4，前2个是 (，后2个是 )。 给定一个长度为 的括号串， 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

数组 前缀和 组合数学
来自：2024年秋招-蚂蚁集...
难度：
0条回答 159浏览

热门推荐

相关试题

小红的可爱括号串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号