Description
括号序列与猪猪侠又大战了起来。
众所周知,括号序列是一个只有(和)组成的序列,我们称一个括号序列S合法,当且仅当:
1.( )是一个合法的括号序列。
2.若A是合法的括号序列,则(A)是合法的括号序列。
3.若A,B是合法的括号序列,则AB是合法的括号序列。
我们考虑match[i]表示从左往右数第i个左括号所对应的是第几个右括号,现在他得到了一个长度为2n的括号序列,给了你m个信息,第i个信息形如ai,bi,表示match[ai]<match[bi],要你还原这个序列。
但是你发现这个猪猪侠告诉你的信息,可能有多个括号序列合法;甚至有可能告诉你一个不存在合法括号序列的信息!
你最近学了取模运算,你想知道答案对998244353(7172^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 1Sample Output
1
42 1 2 0HINT
对于前两个点,是卡特兰数的情况。
对于第三个点,合法的情况只可能是 ()()()。
对于第四个点,合法情况可能是 (()()) 或者 (())()
对于第五个点,由于拓扑关系形成了环,显然无解。
对于 100% 的数据,保证 n < = 300
思路
考虑区间DP
\(dp_{l,r}\)表示满足\([l,r]\)的左区间满足条件的方案数
然后你每次考虑在\([l+1,r]\)的个区间中加入l这个括号
有三种情况:
- 全部包含后面
- 和后面相离
- 把后面分成两半
然后发现我们要处理出两个区间分离没有任何冲突的方案数
这个东西可以对match的二维矩阵做一个前缀和sum
然后\([l_1,r_1]\)\([l_2,r_2]\)的冲突个数就是\(l_1,r_1\)~\(l_2, r_2\)子矩阵的和
#includeusing namespace std;const int N = 310;const int Mod = 998244353;int f[N][N], p[N][N], q[N][N], sum[N][N];int a[N][N], b[N][N];int n, m; int add(int a, int b) { return (a += b) >= Mod ? a - Mod : a;} int mul(int a, int b) { return 1ll * a * b % Mod;} int calc(int x1, int y1, int x2, int y2) { return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];} void solve() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[i][j] = sum[i][j] = 0; bool bk = 0; for (int i = 1; i <= m; i++) { int x, y; scanf("%d %d", &x, &y); sum[x][y] = 1; if (x == y) bk = 1; } if (bk) { printf("0\n"); return; } for (int i = 1; i <= n; i++) { f[i][i] = 1; for (int j = 1; j <= n; j++) { sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1]; } } for (int len = 2; len <= n; len++) { for (int l = 1; l + len - 1 <= n; l++) { int r = l + len - 1; if (!calc(l, l + 1, l, r)) f[l][r] = add(f[l][r], f[l + 1][r]); if (!calc(l + 1, l, r, l)) f[l][r] = add(f[l][r], f[l + 1][r]); for (int k = l + 1; k <= r - 1; k++) { if (!calc(l, l + 1, l, k) && !calc(k + 1, l, r, k)) f[l][r] = add(f[l][r], mul(f[l + 1][k], f[k + 1][r])); } } } printf("%d\n", f[1][n]);}int main() {#ifdef dream_maker freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);#endif int T; scanf("%d", &T); while (T--) solve(); return 0;}