比赛场次 | 513 |
---|---|
比赛名称 | EYOI暨SBOI暑假快乐赛3rd |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2022-06-27 08:30:00 |
结束时间 | 2022-06-27 12:00:00 |
开放分组 | 全部用户 |
注释介绍 | EYOI暨SBOI2022暑假的第三场比赛! 暑假热身赛第三,题都不是很难哦! 细心审题,尽力拿到可以拿到的分数! 注意题目难度不是按照题目编号依次递增! |
题目名称 | 括号序列 |
---|---|
输入输出 | 2021bracket.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 512 MiB |
测试点数 | 20 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
ムラサメ | WWWWWWWWWWWWWWWWWWWW |
0.000 s | 0.00 MiB | 0 |
┭┮﹏┭┮ | WWWTTWTTWTTTTTTTTTTT |
15.026 s | 4.59 MiB | 0 |
小 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并不会做这道题,于是只好请求你来帮忙。
第 1 行,2 个正整数 $n,k$ 。
第 2 行,一个长度为$n$且仅由(、)、*、?构成的字符串S。
输出一个非负整数表示答案对$10^9+7$取模的结果。
7 3 (*??*??
5
如下几种方案是符合规范的:
(**)*() (**(*)) (*(**)) (*)**() (*)(**)
10 2 ???(*??(?)
19
对于 100% 的数据,$1\leq k\leq n\leq 500$。
CSP2021 提高组 Task2