区间dp好题。

---

首先我们并不用把右括号拿进来一起$dp$，而是直接用左括号来$dp$。

然后定义状态fi,jf_{i,j}fi,j​表示区间$[l,r]$的合法方案数。

如果没有限制直接分三种情况讨论就行了。

1. 形如$(AB)$
2. 形如$()AB$
3. 形如$(A)B$

但是现在有了限制。

因此我们枚举决策的时候判当前转移是否合法。

如何判断呢？

我们建立一个数组$stat$。

$stat[a][b]!=0$表示$a$对应的右括号被要求放在$b$对应的右括号前面。

$stat[a][b]=0$表示$a$对应的右括号可以不放在$b$对应的右括号前面。

这样我们就可以判断两个位置的关系啦。

但是我们还需要判断两段区间的位置关系是否合法。

因此我们对$stat$维护一个前缀和数组$sum$。

sum(a,b),(c,d)=0sum_{(a,b),(c,d)}=0sum(a,b),(c,d)​=0表示$a$_{$c$中的数不与$b$}$d$中的数冲突。

然后转移就很方便了。

代码：

#include
    
     using namespace std;inline int read(){
    	int ans=0;	char ch=getchar();	while(!isdigit(ch))ch=getchar();	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans;}const int N=305,mod=998244353;int T,n,m,f[N][N],sum[N][N];inline int calc(int x1,int y1,int x2,int y2){
    return sum[x2][y2]+sum[x1-1][y1-1]-sum[x1-1][y2]-sum[x2][y1-1];}inline int solve(){
    	for(int i=1;i<=n;++i)if(calc(i,i,i,i))return 0;	for(int i=n;i;--i){
    		f[i][i]=1;		for(int j=i+1;j<=n;++j){
    			if(!calc(i,i+1,i,j))(f[i][j]+=f[i+1][j])%=mod;			if(!calc(i+1,i,j,i))(f[i][j]+=f[i+1][j])%=mod;			for(int m=i+1;m