#BZOJ4350. 括号序列再战猪猪侠
-
ID: 2954
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
括号序列再战猪猪侠
No submission language available for this problem.
题目描述
括号序列与猪猪侠又大战了起来。
众所周知，括号序列是一个只有(和)组成的序列，我们称一个括号
序列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)取
模的结果，这个模数是一个质数。
输入格式
第一行一个正整数T,T< = 5，表示数据组数。
对于每组数据，第一行一个n,m，n表示有几个左括号，m表示信息数。
接下来m行，每行两个数ai,bi，1< = ai,bi< = n。
输出格式
对于每组数据，输出一个数表示答案。
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
42
1
2
0
数据范围与约定
对于前两个点，是卡特兰数的情况。
对于第三个点，合法的情况只可能是 ()()()。
对于第四个点，合法情况可能是 (()()) 或者 (())()
对于第五个点，由于拓扑关系形成了环，显然无解。
对于 100% 的数据，保证 n < = 300