列表

详情

NC229944. [CSP2021]括号序列（bracket）

描述

小w在赛场上遇到了这样一个题：一个长度为n且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确定，求这样的括号序列一共有多少个。

身经百战的小w当然一眼就秒了这题，不仅如此，他还觉得一场正式比赛出这么简单的模板题也太小儿科了，于是他把这题进行了加强之后顺手扔给了小c。

具体而言，小w定义“超级括号序列”是由字符 ( 、)、* 组成的字符串，并且对于某个给定的常数k，给出了“符合规范的超级括号序列”的定义如下：
1、均是符合规范的超级括号序列，其中S表示任意一个仅由不超过k个字符 * 组成的非空字符串（以下两条规则中的S均为此含义）；

2、如果字符串A和B均为符合规范的超级括号序列，那么字符串均为符合规范的超级括号序列，其中AB表示把字符串A和字符串B拼接在一起形成的字符串；

3、如果字符串A为符合规范的超级括号序列，那么字符串均为符合规范的超级括号序列。

4、所有符合规范的超级括号序列均可通过上述 3 条规则得到。

例如，若，则字符串 ((**()*(*))*)(***) 是符合规范的超级括号序列，但字符串 *() 、(*()*) 、((**))*) 、(****(*)) 均不是。特别地，空字符串也不被视为符合规范的超级括号序列。

现在给出一个长度为n的超级括号序列，其中有一些位置的字符已经确定，另外一些位置的字符尚未确定（用 ? 表示）。小w希望能计算出：有多少种将所有尚未确定的字符一一确定的方法，使得得到的字符串是一个符合规范的超级括号序列？
可怜的小c并不会做这道题，于是只好请求你来帮忙。
bracket.zip

输入描述

第1行，2个正整数n, k。
第2行，一个长度为n且仅由(、)、*、?构成的字符串S。

输出描述

输出一个非负整数表示答案对取模的结果。

示例1

输入: 

7 3
(*??*??

输出: 

5

说明:

如下几种方案是符合规范的：

(**)*()

(**(*))

(*(**))

(*)**()

(*)(**)

示例2

输入: 

10 2
???(*??(?)

输出: 

19

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 314ms, 内存消耗: 6404K, 提交时间: 2022-08-23 20:28:47 

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=510,P=1e9+7;
ll n,k,f[N][N],g[N][N],S[N][N];char s[N];
signed main()
{
	scanf("%lld%lld",&n,&k);
	scanf("%s",s+1);
	for(ll i=1;i<=n;i++){
		S[i][i-1]=1;
		for(ll j=i;j<=min(n,i+k-1);j++){
			S[i][j]=S[i][j-1]&(s[j]=='?'||s[j]=='*');
			if(!S[i][j])break;
		}
	}
	for(ll len=2;len<=n;len++)
		for(ll l=1;l<=n-len+1;l++){
			ll r=l+len-1;
			if((s[l]=='?'||s[l]=='(')&&(s[r]=='?'||s[r]==')')){
				(f[l][r]+=S[l+1][r-1]+f[l+1][r-1])%=P;
				for(ll k=l+1;k<r-1;k++)
					(f[l][r]+=f[l+1][k]*S[k+1][r-1]+f[k+1][r-1]*S[l+1][k])%=P;
			}
			ll sum=0,z=l;g[l][r]=f[l][r];
			for(ll k=l;k<r;k++){
				(sum+=f[l][k])%=P;
				while(!S[z+1][k])(sum-=f[l][z])%=P,z++;
				(f[l][r]+=g[k+1][r]*sum%P)%=P;
			}
		}
	printf("%lld\n",(f[1][n]+P)%P);
	return 0;
}

上一题

© 2024 nowcoder.com