题意：
现在有n(n<=300)个左括号，要求合理安排n个右括号使其成为一个合法括号序列
但是现在有m(m<=45000)个要求，对于每个要求：
从左往右数第(a_i)个左括号所对应的右括号在第(b_i)个左括号所对应的右括号的前面
最后询问一共有多少种方案数（结果对998244353取模）
题解：
求方案数，基本锁定是dp
考虑区间dp~~(这个我也不知道是怎么想到的难道是n^3的复杂度？？)~
定义(dp_{l,r})表示合法的括号区间[l,r]（l,r指左括号的编号）
考虑用第一对括号(即l)进行转移(设剩下的合法括号串为preans)
- ()preans (dp_{l,r}=dp_{l,r}+dp_{l+1,r};) 条件：[l+1,r]没有限制其对应右括号在l的右括号前面
- (preans) 转移同上; 条件：l没有限制其对应右括号在[l+1,r]的右括号前面
- (pre)ans/(prea)ns/....(即从中间截断)
枚举断点为k:(dp_{l,r}=dp_{l,r}+dp_{l+1,k}*dp_{k+1,r};)
条件：l没有限制其对应右括号在[l+1,k]的右括号的前面并且[k+1,r]没有限制其对应右括号在[l,k]的右括号前面
现在我们关心如何快速判断是否符合条件
对于限制条件的数对((a_i,b_i))(含义如题)
我们记录(mp[a_i][b_i]=1)
然后再用sum[][]对mp[][]做一个二维前缀和
对于一个矩形区域(x,y) (z,w),如果此区域所有数之和为0
则表示不存在[x,z]限制其对应右括号在[y,w]的右括号前面这样的条件
注意：
可能存在自环。这样要输出0.
code:
#include<bits/stdc++.h>
using namespace std;
const int N=305,mod=998244353;
int t,n,m;
int f[N][N],mp[N][N],sum[N][N];
bool vis[N][N];
inline int s(int a1,int b1,int a2,int b2)
{
return sum[a2][b2]-sum[a1-1][b2]-sum[a2][b1-1]+sum[a1-1][b1-1];
}
int dp(int l,int r)
{
int &d=f[l][r];
if(vis[l][r])return d;
vis[l][r]=true;
if(l==r)return d=1;
d=0;
if(!s(l+1,l,r,l))d=(d+dp(l+1,r))%mod;
if(!s(l,l+1,l,r))d=(d+dp(l+1,r))%mod;
for(int k=l+1;k<r;++k)
if(!s(l,l+1,l,k) && !s(k+1,l,r,k))
d=(d+1ll*dp(l+1,k)*dp(k+1,r)%mod)%mod;
return d%mod;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
fill(vis[i]+1,vis[i]+n+1,0),
fill(mp[i]+1,mp[i]+n+1,0),
fill(sum[i]+1,sum[i]+n+1,0);
bool flag=0;
for(int i=1;i<=m;++i)
{
int u,v;scanf("%d%d",&u,&v);
mp[u][v]=1;
if(u==v)flag=1;
}
if(flag){puts("0");continue;}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mp[i][j];
printf("%d
",dp(1,n));
}
return 0;
}