Description
括号序列与猪猪侠又大战了起来。
众所周知，括号序列是一个只有(和)组成的序列，我们称一个括号
序列S合法，当且仅当:
1.( )是一个合法的括号序列。
2.若A是合法的括号序列，则(A)是合法的括号序列。
3.若A，B是合法的括号序列，则AB是合法的括号序列。
我们考虑match[i]表示从左往右数第i个左括号所对应的是第几个右
括号，现在他得到了一个长度为2n的括号序列，给了你m个信息，第i
个信息形如ai,bi，表示match[ai]<match[bi]，要你还原这个序列。
但是你发现这个猪猪侠告诉你的信息，可能有多个括号序列合法；甚
至有可能告诉你一个不存在合法括号序列的信息！
你最近学了取模运算，你想知道答案对998244353(7*17*2^23+1)取
模的结果，这个模数是一个质数。
Input
第一行一个正整数T,T< = 5，表示数据组数。
对于每组数据，第一行一个n,m，n表示有几个左括号，m表示信息数。
接下来m行，每行两个数ai,bi，1< = ai,bi< = n。
Output
对于每组数据，输出一个数表示答案。
Sample Input
5
1 0
5 0
3 2
1 2
2 3
3 2
2 1
2 3
3 3
1 2
2 3
3 1
1 0
5 0
3 2
1 2
2 3
3 2
2 1
2 3
3 3
1 2
2 3
3 1
Sample Output
1
42
1
2
0
42
1
2
0
HINT
对于前两个点，是卡特兰数的情况。
对于第三个点，合法的情况只可能是 ()()()。
对于第四个点，合法情况可能是 (()()) 或者 (())()
对于第五个点，由于拓扑关系形成了环，显然无解。
对于 100% 的数据，保证 n < = 300
Source
http://www.lydsy.com/JudgeOnline/problem.php?id=4350
如果matcha[ai]<match[bi]，那么为了序列能合法，若ai<bi,ai所对应的右括号也一定在bi的左边，若ai>bi，ai和它所对应的右括号，一定被bi所对应的的括号包在中间，我们来考虑一下括号有几种可能吧，很显然有（AB），（）AB，{AB（）可看做同种情况},(A)B,这三种方案，我们枚举一个区间的左括号，f[i][j]表示第i个左括号到第j个左括号能形成多少种方案。
1.如果要符合上面的第一种方案，那么很明显第i个左括号和它对应的右括号不能完全在AB的左边，即第i个左括号对第i+1到j之间的左括号不能有任何一个被提出过match[i]<match[i+1~j]，如果符合的话我们就加上f[i+1][j]。
2.如果要符合第二种方案，那么第i个左括号和它对应的右括号必须完全在AB的左边，即第i个左括号对第i+1到j之间的左括号必须每个都被提出过match[i]<match[i+1~j]，等同于第i+1~j之间的括号对第i个括号没有被提出过match[i+1~j]<match[i],如果符合的话我们就加上f[i+1][j]。
3.如果要符合第三种我们就要进行枚举了，因为我们不知道B序列最右边的左括号是总序列中的第几个括号。枚举一个k来表示A中的最后一个左括号，则B中的开头左括号为k+1，我们要如何满足这种条件呢？有两个注意点，（1）.k+1到j的括号必须全部都在i~k括号的右边。（2）.i+1~k括号必须包含在第i个括号中，即第i个括号不能在他们的右边。
只要满足注意点，它的方案数就可加上两边的乘积。
最最重要的一点来了，我们如何去判断括号在左边右边呢？不要说去一个个枚举。。。我们用一个s数组来储存关系，若match[ai]<match[bi],则s[ai][bi]赋值为1，反之，赋值为0，假设我们现在需要第a~b个左括号全部都在第c~d个括号包括对应的右括号的右边就是说任何一个s[ai~bi][ci~di]都需要为0，那么实际上我们只要知道一个左上角为a,b，右下角为c,d的矩阵中的元素为0，就可以了。那么判断的时候我们只需要用矩阵前缀和就可以用O(1)的复杂度算出矩阵的值从而判断左右关系。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 typedef long long LL; 8 const int SZ = 500; 9 const int mod = 998244353; 10 11 int dp[SZ][SZ]; 12 int sum[SZ][SZ]; 13 14 int getsum(int a,int b,int c,int d) 15 { 16 return sum[c][d] - sum[c][b - 1] - sum[a - 1][d] + sum[a - 1][b - 1]; 17 } 18 19 int ask(int n) 20 { 21 for(int i = 1;i <= n;i ++) 22 if(getsum(i,i,i,i)) return 0; 23 for(int i = n;i >= 1;i --) 24 { 25 dp[i][i] = 1; 26 for(int j = i + 1;j <= n;j ++) 27 { 28 if(!getsum(i,i + 1,i,j)) //(AB) 29 dp[i][j] = (dp[i][j] + dp[i + 1][j]) % mod; 30 if(!getsum(i + 1,i,j,i)) //()AB 31 dp[i][j] = (dp[i][j] + dp[i + 1][j]) % mod; 32 for(int k = i + 1;k < j;k ++) //(A)B 33 if(!getsum(i,i + 1,i,k) && !getsum(k + 1,i,j,i) && !getsum(k + 1,i + 1,j,k)) 34 dp[i][j] = (dp[i][j] + (LL)dp[i + 1][k] * dp[k + 1][j] % mod) % mod; 35 } 36 } 37 return dp[1][n]; 38 } 39 40 void init() 41 { 42 memset(dp,0,sizeof(dp)); 43 memset(sum,0,sizeof(sum)); 44 } 45 46 int main() 47 { 48 int T; 49 scanf("%d",&T); 50 while(T --) 51 { 52 init(); 53 int n,m; 54 scanf("%d%d",&n,&m); 55 for(int i = 1;i <= m;i ++) 56 { 57 int x,y; 58 scanf("%d%d",&x,&y); 59 sum[x][y] = 1; 60 } 61 for(int i = 1;i <= n;i ++) 62 for(int j = 1;j <= n;j ++) 63 sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; 64 printf("%d ",ask(n)); 65 } 66 return 0; 67 }