0

InnitTimmer LV 8 @ 2025-10-10 22:58:21

又是數數題首先我們需要明確一共有多少種合法的狀態也就是答案有多少種可能性

（***）
（）***（）
（***（））
（（）***）

其中所有的*可以為 $0$ 個

然後我們考慮狀態轉移，因為我們是轉移，所以不必把所有狀態全部設成合法的東西

1.設 $dp_{L，R，0}$ 表示在 $[L，R]$ 這個區間內全部是*的方案數 2.設 $dp_{L，R，1}$ 表示在 $[L，R]$ 這個區間內全部是***（）的方案數 3.設 $dp_{L，R，2}$ 表示在 $[L，R]$ 這個區間內全部是（）***的方案數 4.設 $dp_{L，R，3}$ 表示在 $[L，R]$ 這個區間內全部是（S）的方案數，其中只要保證整個串合法即可，不必使S合法 5.設 $dp_{L，R，4}$ 表示在 $[L，R]$ 這個區間內的答案數，可見 $dp_{L，R，3} \in dp_{L，R，4}$ 例如：（***（））、（***）***（***）

1.考慮 $dp_{L，R，0}$ 的轉移，非常簡單，只要判斷連著不超過 $k$ 就可以

dp_{L,R,0}=dp_{L,R-1,0}

前提： $（a_R=$ * $，R-L+1\leq k）$

2.考慮 $dp_{L，R，1}$ 的轉移，因為要保證整個串滿足設的狀態的形狀，則有：

$$dp_{L,R,1}=\sum_{k=L}^{R-1} dp_{L,k,0} \times dp{k+1,R,3} $$

3.考慮 $dp_{L，R，2}$ 的轉移，與 $dp_{L，R，1}$ 類似的：

$$dp_{L,R,2}=\sum_{k=L}^{R-1} dp_{L,k,3} \times dp{k+1,R,0} $$

4.考慮 $dp_{L，R，3}$ 的轉移，分為三種： ①括弧裡面全是*

②括弧裡面是形如答案的

③因為外面是兩個括弧，且裡面有*，在其餘括弧的一側

根據以上三個管道，可以寫出轉移：

dp_{L,R,3}=dp_{L+1,R-1,0}+dp_{L+1,R-1,4}

$$dp_{L,R,3}=\sum_{k=i+1}^{j-2} dp_{i+1,k,0}\times dp_{k+1,j-1,0}+dp_{i+1,k,4}\times dp_{k+1,j-1,4} $$

前提： $a_L=$ （ $，a_R=$ ）

5.考慮 $dp_{L，R，4}$ 的轉移，一定是可以由原來一半狀態 $4$ 加上另一半狀態 $1$ 或 $2$ 和 $3$ ，僅僅這種情況合法

$$dp_{L,R,4}=\sum_{k=i}^ {R-1}dp_ {i,k,4} \times (dp_{k+1,j,1}+dp_{k+1,j,3}) $$

這道題是一道很好的題目，這種設狀態的管道很新穎，並且讓人受益匪淺

#include<iostream>
#include<cstdio>
#define int long long	
using namespace std;
bool Test_MLE_start;
constexpr int N=505,mod=1e9+7;
int _=1,n,kk,dp[N][N][5];
char s[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
bool check(int k,char c){return s[k]=='?'||s[k]==c;}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();scanf("%lld%lld%s",&n,&kk,s+1);
		for(int i=1;i<=n;i++){
			if(check(i,'*')) dp[i][i][0]=1;
		}for(int len=2;len<=n;len++){
			for(int i=1,j=i+len-1;j<=n;i++,j++){
				if(len<=kk&&check(j,'*')) dp[i][j][0]=dp[i][j-1][0];
				if(check(i,'(')&&check(j,')')){
					if(len==2) dp[i][j][3]=1;
					else{
						dp[i][j][3]=(dp[i+1][j-1][0]+dp[i+1][j-1][4])%mod;
						for(int k=i+1;k<=j-2;k++){
							dp[i][j][3]=(dp[i][j][3]+dp[i+1][k][4]*dp[k+1][j-1][0]%mod)%mod;
							dp[i][j][3]=(dp[i][j][3]+dp[i+1][k][0]*dp[k+1][j-1][4]%mod)%mod;
						}
					}
				}dp[i][j][4]=dp[i][j][3]%mod;
				for(int k=i;k<j;k++){
					dp[i][j][1]=(dp[i][j][1]+dp[i][k][0]*dp[k+1][j][3]%mod)%mod;
					dp[i][j][2]=(dp[i][j][2]+dp[i][k][3]*dp[k+1][j][0]%mod)%mod;
					dp[i][j][4]=(dp[i][j][4]+dp[i][k][4]*(dp[k+1][j][1]+dp[k+1][j][3])%mod)%mod;
				}
				
			}
		}printf("%lld\n",dp[1][n][4]);
	}
	return 0;
}

0

InnitTimmer LV 8 @ 2025-10-10 22:57:07

又是数数题

首先我们需要明确一共有多少种合法的状态也就是答案有多少种可能性

(***)
()***()
(***())
(()***)

其中所有的*可以为 $0$ 个

然后我们考虑状态转移，因为我们是转移，所以不必把所有状态全部设成合法的东西

设 $dp_{L,R,0}$ 表示在 $[L,R]$ 这个区间内全部是* 的方案数
设 $dp_{L,R,1}$ 表示在 $[L,R]$ 这个区间内全部是***() 的方案数
设 $dp_{L,R,2}$ 表示在 $[L,R]$ 这个区间内全部是()*** 的方案数
设 $dp_{L,R,3}$ 表示在 $[L,R]$ 这个区间内全部是(S) 的方案数，其中只要保证整个串合法即可，不必使S合法
设 $dp_{L,R,4}$ 表示在 $[L,R]$ 这个区间内的答案数，可见 $dp_{L,R,3} \in dp_{L,R,4}$

例如：(***())、(***)***(***)

考虑 $dp_{L,R,0}$ 的转移，非常简单，只要判断连着不超过 $k$ 就可以

dp_{L,R,0}=dp_{L,R-1,0}

前提： $(a_R=$ * $,R-L+1\leq k)$

考虑 $dp_{L,R,1}$ 的转移，因为要保证整个串满足设的状态的形状，则有：

$$dp_{L,R,1}=\sum_{k=L}^{R-1} dp_{L,k,0} \times dp{k+1,R,3} $$

考虑 $dp_{L,R,2}$ 的转移，与 $dp_{L,R,1}$ 类似的：

$$dp_{L,R,2}=\sum_{k=L}^{R-1} dp_{L,k,3} \times dp{k+1,R,0} $$

考虑 $dp_{L,R,3}$ 的转移，分为三种：

① 括号里面全是 *

② 括号里面是形如答案的

③因为外面是两个括号，且里面有*，在其余括号的一侧

根据以上三个方式，可以写出转移：

dp_{L,R,3}=dp_{L+1,R-1,0}+dp_{L+1,R-1,4}

$$dp_{L,R,3}=\sum_{k=i+1}^{j-2} dp_{i+1,k,0}\times dp_{k+1,j-1,0}+dp_{i+1,k,4}\times dp_{k+1,j-1,4} $$

前提： $a_L=$ ( $,a_R=$ )

考虑 $dp_{L,R,4}$ 的转移，一定是可以由原来一半状态 $4$ 加上另一半状态 $1$ 或 $2$ 和 $3$ ，仅仅这种情况合法

$$dp_{L,R,4}=\sum_{k=i}^{R-1}dp_{i,k,4} \times (dp_{k+1,j,1}+dp_{k+1,j,3}) $$

这道题是一道很好的题目，这种设状态的方式很新颖，并且让人受益匪浅

#include<iostream>
#include<cstdio>
#define int long long	
using namespace std;
bool Test_MLE_start;
constexpr int N=505,mod=1e9+7;
int _=1,n,kk,dp[N][N][5];
char s[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
bool check(int k,char c){return s[k]=='?'||s[k]==c;}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();scanf("%lld%lld%s",&n,&kk,s+1);
		for(int i=1;i<=n;i++){
			if(check(i,'*')) dp[i][i][0]=1;
		}for(int len=2;len<=n;len++){
			for(int i=1,j=i+len-1;j<=n;i++,j++){
				if(len<=kk&&check(j,'*')) dp[i][j][0]=dp[i][j-1][0];
				if(check(i,'(')&&check(j,')')){
					if(len==2) dp[i][j][3]=1;
					else{
						dp[i][j][3]=(dp[i+1][j-1][0]+dp[i+1][j-1][4])%mod;
						for(int k=i+1;k<=j-2;k++){
							dp[i][j][3]=(dp[i][j][3]+dp[i+1][k][4]*dp[k+1][j-1][0]%mod)%mod;
							dp[i][j][3]=(dp[i][j][3]+dp[i+1][k][0]*dp[k+1][j-1][4]%mod)%mod;
						}
					}
				}dp[i][j][4]=dp[i][j][3]%mod;
				for(int k=i;k<j;k++){
					dp[i][j][1]=(dp[i][j][1]+dp[i][k][0]*dp[k+1][j][3]%mod)%mod;
					dp[i][j][2]=(dp[i][j][2]+dp[i][k][3]*dp[k+1][j][0]%mod)%mod;
					dp[i][j][4]=(dp[i][j][4]+dp[i][k][4]*(dp[k+1][j][1]+dp[k+1][j][3])%mod)%mod;
				}
				
			}
		}printf("%lld\n",dp[1][n][4]);
	}
	return 0;
}

0

lzd2010 LV 8 @ 2025-10-10 14:44:43

考虑区间 DP。由于合法状态比较多，如果只使用 $dp_{l,r}$ 表示 $[l,r]$ 的合法超级括号序列方案数是不够的，所以我们要考虑更多情况。

$dp_{l,r,0}$ 表示 $[l,r]$ 全部为 $\texttt{*}$ 的方案数。
$dp_{l,r,1}$ 表示 $[l,r]$ 为单个的合法超级括号序列方案数，例如 $\texttt{()**()}$ 这种复合的就不算
$dp_{l,r,2}$ 表示 $[l,r]$ 为单个的合法超级括号序列且前面有若干个 $\texttt{*}$ 的方案数
$dp_{l,r,3}$ 表示 $[l,r]$ 为单个的合法超级括号序列且后面有若干个 $\texttt{*}$ 的方案数
$dp_{l,r,4}$ 表示 $[l,r]$ 这一段所有合法超级括号序列方案数，包括单个的和复合的。

然后转移就行了

首先是初值，当 $a_i$ 为 $\texttt{*}$ 时， $dp_{i,i,0}=1$
题目说 $\texttt{?}$ 可以代替别的字符，以下不再赘述。
对于 $dp_{l,r,0}$ ，如果 $a_r$ 为 $\texttt{*}$ 且 $[l,r]$ 长度在 $k$ 以内则可以从 $dp_{l,r-1,0}$ 转移。
对于 $dp_{l,r,1}$ ，只有 $a_l$ 为 $\texttt{(}$ 且 $a_r$ 为 $\texttt{)}$ 时才能转移，括号里面的内容可以有前缀 $\texttt{*}$ ，可以有后缀 $\texttt{*}$ ，也可以没有 $\texttt{*}$ ，但两边不能都有 $\texttt{*}$ 。
对于 $dp_{l,r,2}$ 和 $dp_{l,r,3}$ ，枚举那个分界点，注意这里 $\texttt{*}$ 的个数不能超过 $k$ 。
对于 $dp_{l,r,4}$ ，首先加上 $dp_{l,r,1}$ ，然后我们枚举分界点，分界点前面的可以复合，分界点后面的不能复合但可以有前缀 $\texttt{*}$ 。

答案显然为 $dp_{1,n,4}$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int n,k;
string a;
int dp[505][505][5];
inline bool chk(int i,char c) {
	return (a[i]=='?'||a[i]==c);
}
signed main() {
	cin>>n>>k>>a;
	a=" "+a;
	for(int i=1; i<=n; ++i) {
		if(chk(i,'*')) dp[i][i][0]=1;
	}
	for(int len=2; len<=n; ++len) {
		for(int l=1; l+len-1<=n; ++l) {
			int r=l+len-1;
			if(len<=k&&chk(r,'*')) dp[l][r][0]=dp[l][r-1][0];
			if(chk(l,'(')&&chk(r,')')) {
				int x=l+1,y=r-1;
				if(x>y) dp[l][r][1]=1;
				else {
					dp[l][r][1]=dp[x][y][0]+dp[x][y][4];
					for(int i=1; i<=min(k,len-2); ++i) {
						dp[l][r][1]=(dp[l][r][1]+dp[x][y-i][4]*dp[y-i+1][y][0])%mod;
						dp[l][r][1]=(dp[l][r][1]+dp[x+i][y][4]*dp[x][x+i-1][0])%mod;
					}
				}
			}
			for(int i=1; i<=min(k,len-1); ++i) {
				dp[l][r][2]=(dp[l][r][2]+dp[l][l+i-1][0]*dp[l+i][r][1])%mod;
				dp[l][r][3]=(dp[l][r][3]+dp[l][r-i][1]*dp[r-i+1][r][0])%mod;
			}
			dp[l][r][4]=dp[l][r][1];
			for(int i=l; i<r; ++i) {
				dp[l][r][4]=(dp[l][r][4]+dp[l][i][4]*(dp[i+1][r][1]+dp[i+1][r][2])%mod)%mod;
			}
		}
	}
	cout<<dp[1][n][4];
	return 0;
}

虽然能过

但是

我思路

可能

假了

大家快来 hack 我。

Tim_justforsure @ 2025-10-10 15:46:26

感觉很对

Tim_justforsure @ 2025-10-10 16:02:29

带注释的代码，更适合食用

#include<iostream>
#include<cstdio>
#include<algorithm>

#define N 502
#define mod 1000000007
#define int long long

using namespace std;

inline int read(){
	int x=0,f=1; char c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar(); 
	}
	return x*f; 
} 

int n,kk, dp[N][N][10];
char a[N];



signed main(){
//	freopen("bracket4.in","r",stdin);
//	freopen("bracket.out","w",stdout);                    	
	n=read();kk=read();scanf(" %s",a+1);
	for (int i=1;i<=n;i++){
		if (a[i]=='*'||a[i]=='?') dp[i][i][0]=1;
	}
	for (int len=2;len<=n;len++){
		for (int l=1;l+len-1<=n;l++){
			int r=l+len-1;
			if ((a[r]=='*'||a[r]=='?') && len<=kk){
				dp[l][r][0]=dp[l][r-1][0]; // ***
			}
			if ((a[l]=='('||a[l]=='?') && (a[r]==')'||a[r]=='?')){//在外面套括号
				if (len==2) dp[l][r][1]=1; // ()
				else{
					dp[l][r][1]=(dp[l+1][r-1][0]+dp[l+1][r-1][4])%mod; // (***) / (A)
					for (int k=l+1;k<=r-2;k++){
						dp[l][r][1]=(dp[l][r][1] + dp[l+1][k][0]*dp[k+1][r-1][4])%mod; // (***A)
						dp[l][r][1]=(dp[l][r][1] + dp[l+1][k][4]*dp[k+1][r-1][0])%mod; // (A***)
					}
				}
			}
			dp[l][r][4]=dp[l][r][1];
			for (int k=l;k<=r-1;k++){
				dp[l][r][2]=(dp[l][r][2] + dp[l][k][0]*dp[k+1][r][1])%mod; // ***(A)
				dp[l][r][3]=(dp[l][r][3] + dp[l][k][1]*dp[k+1][r][0])%mod; // (A)***
			}
			for (int k=l;k<=r-1;k++){
				dp[l][r][4]=(dp[l][r][4] + dp[l][k][4]*(dp[k+1][r][1]+dp[k+1][r][2]))%mod; // A (B) / A ***(B)
			}
		}
	}
	printf("%lld",dp[1][n][4]); 
	return 0;
}

-1

InnitTimmer LV 8 @ 2025-10-10 23:00:18

It's another counting problem

Firstly, we need to clarify how many legal states there are, that is, how many possibilities there are for the answer

(***)
()***()
(***())
(()***) Among them, all '*' can be $0$ pieces Then we consider state transitions, as we are transitions, there is no need to set all states as legal
Let $dp_ {L, R, 0}$ represent the number of schemes in the interval $[L, R]$ that are all '*'
Let $dp_ {L, R, 1}$ represent the number of schemes in the interval $[L, R]$ that are all * * ()
Let $dp_ {L, R, 2}$ represent the number of schemes in the interval $[L, R]$ that are all () * * *
Let $dp_ {L, R, 3}$ represent the number of schemes in the interval $[L, R]$ that are all (S), as long as the entire string is valid, there is no need to make S legal
Let $dp_ {L, R, 4}$ represent the number of answers in the interval $[L, R]$ , as shown in $dp_ {L, R, 3} \ in dp_ {L, R, 4}$

For example: (* * * ()), (* * *) * * (* * *)

Consider the transfer of $dp_ {L, R, 0}$ , which is very simple, as long as it is determined that the connection does not exceed $k$

dp_{L,R,0}=dp_{L,R-1,0}

Prerequisite: $(a_R=$ * $, R-L+1 \leq k)$

Consider the transition of $dp_ {L, R, 1}$ , because to ensure that the entire string satisfies the shape of the given state, there are:

$$dp_{L,R,1}=\sum_{k=L}^{R-1} dp_{L,k,0} \times dp{k+1,R,3} $$

Consider the transfer of $dp_ {L, R, 2}$ , similar to $dp_ {L, R, 1}$ :

$$dp_{L,R,2}=\sum_{k=L}^{R-1} dp_{L,k,3} \times dp{k+1,R,0} $$

Consider the transfer of $dp_ {L, R, 3}$ , which can be divided into three types: ① Inside the parentheses are all*

② The answer is in parentheses

③ Because there are two parentheses on the outside and '*' inside, on one side of the remaining parentheses According to the above three methods, the transfer can be written as follows:

dp_{L,R,3}=dp_{L+1,R-1,0}+dp_{L+1,R-1,4}

$$dp_{L,R,3}=\sum_{k=i+1}^{j-2} dp_{i+1,k,0}\times dp_{k+1,j-1,0}+dp_{i+1,k,4}\times dp_{k+1,j-1,4} $$

Prerequisite: $a_L=$ ( $, a_R=$ ) 6. Considering the transition of $dp_ {L, R, 4}$ , it must be possible to add half of the original state of $4$ to the other half of the state of $1$ or $2$ and $3$ , and only in this case is it legal

$$dp_{L,R,4}=\sum_{k=i}^ {R-1}dp_ {i,k,4} \times (dp_{k+1,j,1}+dp_{k+1,j,3}) $$

This question is a great one, and the way of setting states is very innovative and beneficial.

#include<iostream>
#include<cstdio>
#define int long long	
using namespace std;
bool Test_MLE_start;
constexpr int N=505,mod=1e9+7;
int _=1,n,kk,dp[N][N][5];
char s[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
bool check(int k,char c){return s[k]=='?'||s[k]==c;}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();scanf("%lld%lld%s",&n,&kk,s+1);
		for(int i=1;i<=n;i++){
			if(check(i,'*')) dp[i][i][0]=1;
		}for(int len=2;len<=n;len++){
			for(int i=1,j=i+len-1;j<=n;i++,j++){
				if(len<=kk&&check(j,'*')) dp[i][j][0]=dp[i][j-1][0];
				if(check(i,'(')&&check(j,')')){
					if(len==2) dp[i][j][3]=1;
					else{
						dp[i][j][3]=(dp[i+1][j-1][0]+dp[i+1][j-1][4])%mod;
						for(int k=i+1;k<=j-2;k++){
							dp[i][j][3]=(dp[i][j][3]+dp[i+1][k][4]*dp[k+1][j-1][0]%mod)%mod;
							dp[i][j][3]=(dp[i][j][3]+dp[i+1][k][0]*dp[k+1][j-1][4]%mod)%mod;
						}
					}
				}dp[i][j][4]=dp[i][j][3]%mod;
				for(int k=i;k<j;k++){
					dp[i][j][1]=(dp[i][j][1]+dp[i][k][0]*dp[k+1][j][3]%mod)%mod;
					dp[i][j][2]=(dp[i][j][2]+dp[i][k][3]*dp[k+1][j][0]%mod)%mod;
					dp[i][j][4]=(dp[i][j][4]+dp[i][k][4]*(dp[k+1][j][1]+dp[k+1][j][3])%mod)%mod;
				}
				
			}
		}printf("%lld\n",dp[1][n][4]);
	}
	return 0;
}

4 条题解

然后转移就行了

虽然能过

但是

我思路

可能

假了

大家快来 hack 我。

[CSP-S 2021] 括号序列

信息

状态

开发

支持

4 条题解

然后转移就行了

虽然能过

但是

我思路

可能

假了

大家快来 hack 我。

[CSP-S 2021] 括号序列

信息

状态

开发

支持

还没有账户？

登录