传送门
区间dp好题。
首先我们并不用把右括号拿进来一起dpdpdp，而是直接用左括号来dpdpdp。
然后定义状态fi,jf_{i,j}fi,j表示区间[l,r][l,r][l,r]的合法方案数。
如果没有限制直接分三种情况讨论就行了。
- 形如(AB)(AB)(AB)
- 形如()AB()AB()AB
- 形如(A)B(A)B(A)B
但是现在有了限制。
因此我们枚举决策的时候判当前转移是否合法。
如何判断呢？
我们建立一个数组statstatstat。
stat[a][b]!=0stat[a][b]!=0stat[a][b]!=0表示aaa对应的右括号被要求放在bbb对应的右括号前面。
stat[a][b]=0stat[a][b]=0stat[a][b]=0表示aaa对应的右括号可以不放在bbb对应的右括号前面。
这样我们就可以判断两个位置的关系啦。
但是我们还需要判断两段区间的位置关系是否合法。
因此我们对statstatstat维护一个前缀和数组sumsumsum。
sum(a,b),(c,d)=0sum_{(a,b),(c,d)}=0sum(a,b),(c,d)=0表示aaa$c$中的数不与$b$ddd中的数冲突。
然后转移就很方便了。
代码：
#include<bits/stdc++.h>
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<j;++m)if(!calc(m+1,i+1,j,m)&&!calc(i,i+1,i,m)&&!calc(m+1,i,j,i))(f[i][j]+=1ll*f[i+1][m]*f[m+1][j]%mod)%=mod;
}
}
return f[1][n];
}
int main(){
T=read();
while(T--){
n=read(),m=read();
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)sum[i][j]=f[i][j]=0;
for(int i=1,a,b;i<=m;++i)a=read(),b=read(),sum[a][b]=1;
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)sum[i][j]=sum[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
printf("%d\n",solve());
}
return 0;
}