本文共 3346 字，大约阅读时间需要 11 分钟。

题目

题目描述

今天，接触信息学不久的小$A$刚刚学习了卡特兰数。

卡特兰数的一个经典定义是，将$n$个数依次入栈，合法的出栈序列个数。

小$A$觉得这样的情况太平凡了。于是，他给出了$m$组限制，每个限制形如$(f_i,g_i)$，表示$f_i$不能在$g_i$之后出栈。
他想求出：在满足了这$m$组限制的前提下，共有多少个合法的出栈序列。他不喜欢大数，你只需要求出答案在模$998244353$意义下的值即可。

输入格式

输入第一行为两个非负整数，$n$、$m$，含义题面已给出。
接下来$m$行，每行两个正整数，$(f,g)$ 表示一组限制。

输出格式

输出一行，为一个非负整数，表示你求得的答案 $mod998244353$。

样例输入

3 12 3

样例输出

3

样例解释
可以验证 { 1 , 2 , 3 } \{1,2,3\} { 1,2,3}， { 2 , 1 , 3 } \{2,1,3\} { 2,1,3}， { 2 , 3 , 1 } \{2,3,1\} { 2,3,1}都是合乎条件的。

数据规模

对于全部的数据，保证$n\le 300$，$m\le \frac{n(n-1)}{2}$，$f_i、g_i\le n$。

题解

题目大意：$n$个数以此入栈，问在满足$m$个形如$f_i$不能在$g_i$后出栈的限制的出栈序列数

45%

我们知道卡特兰数有个推导公式是$f_i={\sum }_{i=1}^n{f}_i\times f_{n-i-1}$,这个公式实际上是枚举了最后出栈的数

那么扩展到这题，我们将$dp$转换为区间$dp$，枚举$k$为最后出栈的数，那么有两种情况不合法：$f=k$或者$f>k>g$。当$f=k$的时候，$f$是最后出栈的，显然不合法。而我们知道，小于$k$总是比大于$k$的先出栈，所以当$f>k>g$时也是不合法的

设$f[i][j]$表示$i$到$j$这个区间的合法出栈序列，那么在上述两种不合法的情况不成立的情况下，$f[i][j]+=f[i][k-1]\times f[k+1][j]$

时间复杂度$O(n^{3}m)$，预计得分$45$

100%

考虑优化$dp$，在$O(1)$的时间内判断合不合法。不合法条件$f>k>g$成立，说明$f>g$，那么在读入时$f>g$的放入平面直角坐标系中，坐标$(f,g)$，那么可以前缀和优化

记录前缀和$sm[i][j]$和$l[i][j]$，分别记录$f>g$以及所有的点，用来判断$f>k>g$和$f=k$的情况

构造一个矩形

其中$i,j,k$分别是区间起点，终点，以及最后出栈的数

$f=k$说明$l[k][j]-l[k][i-1]>0$，而如果矩形$sm(i,i,j,k-1)-sm(i,i,k,j)>0$，说明有$f>k>g$的情况，这两种情况都是不合法的

这样的话时间复杂度优化到了$O(n^3)$，预计得分$100$

Code

#include<cstdio>#define mod 998244353#define N 310#define ll long longusing namespace std;ll n,m,f[N][N],sm[N][N],al[N][N];ll get(ll x,ll y,ll p,ll q) {   return sm[x][y]-sm[x][q-1]-sm[p-1][y]+sm[p-1][q-1];}int main(){   	freopen("catalan.in","r",stdin);	freopen("catalan.out","w",stdout);	scanf("%lld%lld",&n,&m);	for (ll i=1,x,y;i<=m;++i)	{   		scanf("%lld%lld",&x,&y);		if (x!=y)		{   			if (x>y) ++sm[x][y];			++al[x][y];		}	}	for (ll i=1;i<=n;++i)		for (ll j=1;j<=n;++j)		{   			sm[i][j]=sm[i][j]+sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1];			al[i][j]=al[i][j]+al[i][j-1];		}	for (ll i=1;i<=n;++i)		f[i][i]=f[i+1][i]=f[i][i-1]=1;	for (ll len=2;len<=n;++len)		for (ll i=1;i+len-1<=n;++i)		{   			ll j=i+len-1;			for (ll k=i;k<=j;++k)			{   				ll x;				if (k>i) x=get(j,k-1,i,i)-get(k,j,i,i);				else x=0;				ll y=al[k][j]-al[k][i-1];				if (x<=0&&y<=0) f[i][j]=(f[i][j]+f[i][k-1]*f[k+1][j]%mod)%mod;			}		}	printf("%lld\n",f[1][n]);	fclose(stdin);	fclose(stdout);	return 0;}