310417: CF1830C. Hyperregular Bracket Strings

Memory Limit：256 MB Time Limit：3 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

C. Hyperregular Bracket Stringstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given an integer $n$ and $k$ intervals. The $i$-th interval is $[l_i,r_i]$ where $1 \leq l_i \leq r_i \leq n$.

Let us call a regular bracket sequence$^{\dagger,\ddagger}$ of length $n$ hyperregular if for each $i$ such that $1 \leq i \leq k$, the substring $\overline{s_{l_i} s_{l_{i}+1} \ldots s_{r_i}}$ is also a regular bracket sequence.

Your task is to count the number of hyperregular bracket sequences. Since this number can be really large, you are only required to find it modulo $998\,244\,353$.

$^\dagger$ A bracket sequence is a string containing only the characters "(" and ")".

$^\ddagger$ A bracket sequence is called regular if one can turn it into a valid math expression by adding characters + and 1. For example, sequences (())(), (), (()(())) and the empty string are regular, while )(, ((), and (()))( are not.

Input

Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 3 \cdot 10^5$, $0 \le k \le 3 \cdot 10^5$) — the length of the hyperregular bracket sequences and the number of intervals respectively.

The following $k$ lines of each test case contains two integers $l_i$ and $r_i$ ($1 \le l \le r \le n$).

It is guaranteed that the sum of $n$ across all test cases does not exceed $3 \cdot 10^5$ and the sum of $k$ across all test cases does not exceed $3 \cdot 10^5$.

Output

For each test case, output the number of hyperregular bracket sequences modulo $998\,244\,353$.

ExampleInput
7
6 0
5 0
8 1
1 3
10 2
3 4
6 9
1000 3
100 701
200 801
300 901
28 5
1 12
3 20
11 14
4 9
18 19
4 3
1 4
1 4
1 4
Output
5
0
0
4
839415253
140
2
Note
  • For the first testcase, the $5$ hyperregular bracket strings of length $6$ are: ((())), (()()), (())(), ()(()) and ()()().
  • For the second testcase, there are no regular bracket strings of length $5$, and consequently, there are no hyperregular bracket strings of length $5$.
  • For the third testcase, there are no hyperregular bracket strings of length $8$ for which the substring $[1 \ldots 3]$ is a regular bracket string.
  • For the fourth testcase, there $4$ hyperregular bracket strings are: ((())(())), ((())()()), ()()((())) and ()()(()())

Input

题意翻译

## 题目描述 给定一个数 $n$ 和 $k$ 个区间 $\left[l_i,r_i\right]\in [1,n]$。 我们定义，对于一个长度为 $n$ 的，仅由 ```(``` 和 ```)``` 组成的合法括号序列，如果它的每一个区间 $\left[l_i,r_i\right]$ 内的子串都是合法括号序列，那么这个括号序列是**好的**。 求**好的**括号序列的数量，答案对 $998244353$ 取模。 ## 输入格式 每个数据点第一行为一个数 $t\ (1\le t\le 10^5)$，表示数据组数。 每组数据第一行为两个数 $n,k\ (1\le n\le 3\cdot 10^5,1\le k\le3\cdot 10 ^5)$，意义同题目描述中的 $n,k$。 接下来的 $k$ 行中，第 $i$ 行为两个数 $l_i,r_i$，表示题目描述中给定的第 $i$ 个区间。 ## 输出格式 共 $t$ 行，第 $i$ 行表示第 $i$ 组数据的答案对 $998244353$ 取模后的结果 ## 样例说明 以样例的第四组数据为例，答案代表的 $4$ 个好的括号序列分别是： ``` ((())(())) ((())()()) ()()((())) ()()(()()) ``` 而 ```)(())(())(``` 不是答案之一，因为它不是一个合法的括号序列（最左端与最右端的括号未配对） ```(())((()))``` 也不是答案之一，因为它的 $[3,4]$ 表示的子串 ```))``` 不是一个合法的括号序列 ```((()(())))``` 也不是答案之一，因为它的 $[6,9]$ 表示的子串 ```()))``` 不是一个合法的括号序列

Output

题目大意：超级规则括号字符串

有一个整数n和k个区间。第i个区间是[l_i,r_i]，其中1≤l_i≤r_i≤n。

我们将长度为n的规则括号序列称为超级规则，如果对于每个1≤i≤k，子字符串s_{l_i} s_{l_i+1} … s_{r_i}也是一个规则括号序列。

任务是计算超级规则括号序列的数量。由于这个数字可能非常大，你只需要找到它模998,244,353。

输入输出数据格式：

输入：

每个测试包含多个测试用例。输入的第一行包含一个整数t（1≤t≤10^5）——测试用例的数量。接下来是t个测试用例的描述。

每个测试用例的第一行包含两个整数n和k（1≤n≤3×10^5，0≤k≤3×10^5）——超级规则括号序列的长度和区间的数量。

接下来的k行，每行包含两个整数l_i和r_i（1≤l≤r≤n）。

保证所有测试用例的n之和不超过3×10^5，k之和不超过3×10^5。

输出：

对于每个测试用例，输出超级规则括号序列的数量模998,244,353。题目大意：超级规则括号字符串 有一个整数n和k个区间。第i个区间是[l_i,r_i]，其中1≤l_i≤r_i≤n。 我们将长度为n的规则括号序列称为超级规则，如果对于每个1≤i≤k，子字符串s_{l_i} s_{l_i+1} … s_{r_i}也是一个规则括号序列。 任务是计算超级规则括号序列的数量。由于这个数字可能非常大，你只需要找到它模998,244,353。 输入输出数据格式： 输入： 每个测试包含多个测试用例。输入的第一行包含一个整数t（1≤t≤10^5）——测试用例的数量。接下来是t个测试用例的描述。 每个测试用例的第一行包含两个整数n和k（1≤n≤3×10^5，0≤k≤3×10^5）——超级规则括号序列的长度和区间的数量。 接下来的k行，每行包含两个整数l_i和r_i（1≤l≤r≤n）。 保证所有测试用例的n之和不超过3×10^5，k之和不超过3×10^5。 输出： 对于每个测试用例，输出超级规则括号序列的数量模998,244,353。

Source/Category

加入题单

上一题 下一题 算法标签：