Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5607 --括号序列（bracket）
5607: 括号序列（bracket）
警告！
题目
状态
题解(1)
题目描述
小 w 在赛场上遇到了这样一个题：一个长度为 $n$ 且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确定，求这样的括号序列一共有多少个。 身经百战的小 w 当然一眼就秒了这题，不仅如此，他还觉得一场正式比赛出这么简单的模板题也太小儿科了，于是他把这题进行了加强之后顺手扔给了小 c。 具体而言，小 w 定义“超级括号序列”是由字符 `(`、`)`、`*` 组成的字符串，并且对于某个给定的常数 $k$，给出了“符合规范的超级括号序列”的定义如下： 1. `()`、`(S)` 均是符合规范的超级括号序列，其中 `S` 表示任意一个仅由**不超过** $ {k}$ **个**字符 `*` 组成的非空字符串（以下两条规则中的 `S` 均为此含义）； 2. 如果字符串 `A` 和 `B` 均为符合规范的超级括号序列，那么字符串 `AB`、`ASB` 均为符合规范的超级括号序列，其中 `AB` 表示把字符串 `A` 和字符串 `B` 拼接在一起形成的字符串； 3. 如果字符串 `A` 为符合规范的超级括号序列，那么字符串 `(A)`、`(SA)`、`(AS)` 均为符合规范的超级括号序列。 4. 所有符合规范的超级括号序列均可通过上述 3 条规则得到。 例如，若 $k = 3$，则字符串 `((**()*(*))*)(***)` 是符合规范的超级括号序列，但字符串 `*()`、`(*()*)`、`((**))*)`、`(****(*))` 均不是。特别地，空字符串也不被视为符合规范的超级括号序列。 现在给出一个长度为 $n$ 的超级括号序列，其中有一些位置的字符已经确定，另外一些位置的字符尚未确定（用 `?` 表示）。小 w 希望能计算出：有多少种将所有尚未确定的字符一一确定的方法，使得得到的字符串是一个符合规范的超级括号序列？ 可怜的小 c 并不会做这道题，于是只好请求你来帮忙。
输入
第一行，两个正整数 $n, k$。 第二行，一个长度为 $n$ 且仅由 `(`、`)`、`*`、`?` 构成的字符串 $S$。
输出
输出一个非负整数表示答案对 ${10}^9 + 7$ 取模的结果。
样例输入输出
输入#1
复制
7 3 (*??*??
输出#1
复制
5
输入#2
复制
10 2 ???(*??(?)
输出#2
复制
19
提示
**【样例解释 #1】** 如下几种方案是符合规范的： ```plain (**)*() (**(*)) (*(**)) (*)**() (*)(**) ``` **【数据范围】** | 测试点编号 | $n \le$ | 特殊性质 | |:-:|:-:|:-:| | $1 \sim 3$ | $15$ | 无 | | $4 \sim 8$ | $40$ | 无 | | $9 \sim 13$ | $100$ | 无 | | $14 \sim 15$ | $500$ | $S$ 串中仅含有字符 `?` | | $16 \sim 20$ | $500$ | 无 | 对于 $100 \%$ 的数据，$1 \le k \le n \le 500$。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
未评定
标签
点击显示
递交数
8
已通过
3
通过率
38%
时间限制
1 秒
内存限制
512 MB
来源
2021CSP S2
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和