自动搬运

查看原文

来自洛谷，原作者为

	Redamancy_Lydic 其实我……

搬运于2025-08-24 22:59:32，当前版本为作者最后更新于2024-10-28 20:20:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

根据题目要求，容易想到区间计数动态规划。

我们只考虑左括号，设 $dp_{l,r}$ 表示当前考虑从第 $l$ 到第 $r$ 个左括号时的方案数，注意，这里的状态同时包含了这些左括号对应的右括号。

考虑转移，我们设 A 为一个合法括号串，它表示的左括号区间是 $[l,r]$，可以很自然的分三种情况：

• (A)，此时需满足 $[l,r]$ 中所有右括号都没有要求大于第 $l-1$ 个左括号的右括号的限制。

• ()A，此时和上面类似，需满足 $[l,r]$ 中所有右括号都没有要求小于第 $l-1$ 个左括号的右括号的限制。

• (A，同时把 A 从中间断开插入右括号，设当前枚举的断点为 $k$，此时需满足 $[l,k]$ 中所有右括号都没有要求大于第 $l-1$ 个左括号的右括号的限制，以及 $[l-1,k]$ 中所有右括号都没有要求大于区间 $[k+1,r]$ 中所有左括号的右括号的限制。

对于这些限制的快速判断我们可以维护一个矩阵，每条信息相当于矩阵上的一个点，这样对于前文的要求可以快速用二位前缀和的值的存在与否判断是否全部满足。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int w=1,s=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
	return w*s;
}
const int mod=998244353;	
const int maxn=500+10;
const int inf=1e13+7;
int n,m;
int dp[maxn][maxn],sum[maxn][maxn],a[maxn][maxn];
int ask(int l1,int r1,int l2,int r2)
{return sum[l2][r2]-sum[l1-1][r2]-sum[l2][r1-1]+sum[l1-1][r1-1];}
void Main()
{
	n=read(),m=read();
	for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)a[i][j]=sum[i][j]=0;
	bool ff=1;
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		a[x][y]=1;
		if(x==y)ff=0;
	}
	if(!ff){puts("0");return ;}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
		}
	}
	memset(dp,0,sizeof dp);
	for(int i=1;i<=n;i++)dp[i][i]=1;
	for(int len=2;len<=n;len++)
	{
		for(int l=1;l<=n-len+1;l++)
		{
			int r=l+len-1;
			if(!ask(l,l+1,l,r))(dp[l][r]+=dp[l+1][r])%=mod;
			if(!ask(l+1,l,r,l))(dp[l][r]+=dp[l+1][r])%=mod;
			for(int k=l+1;k<r;k++)
			{ 
				if(!ask(l,l+1,l,k)&&!ask(k+1,l,r,k))
				{
					dp[l][r]=(dp[l][r]+dp[l+1][k]*dp[k+1][r]%mod)%mod;
				}
			}
		}
	}
	printf("%lld\n",dp[1][n]);
}
signed main()
{
#ifdef Lydic
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
//  #else
//   	freopen("Stone.in","r",stdin);
//   	freopen("Stone.out","w",stdout);
#endif
	int T=read();
	while(T--)Main();
    return 0;
}