[R54F]可爱的多级括号序列 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定两个正整数 $n,m$（$n \ge m$），请输出有多少个可爱的多级括号序列包含恰好 $n$ 对 $1$ 级括号、$n-1$ 对 $2$ 级括号、……、$n-m+1$ 对 $m$ 级括号，由于答案可能很大，请输出答案对 $998244353$ 取模的结果。

一个多级括号序列定义为一个只包含任意级别的左括号和任意级别的右括号的字符串。

我们称一个长度为 $k$ 的多级括号序列 $S$ 是平衡的，当且仅当它满足以下三种条件之一：

• $S$ 是一个空字符串。
• $k \ge 2$，且 $S_1$ 为左括号，且 $S_k$ 为右括号，且 $S_1$ 和 $S_k$ 为同级括号，且字符串 $S_2,S_3,\dots,S_{k-1}$ 是一个平衡的多级括号序列。
• 存在两个平衡的非空多级括号序列 $A,B$，满足 $S=A+B$，其中 $A+B$ 表示将 $B$ 拼接到 $A$ 末尾后得到的新字符串。

同时对于一个长度为 $k$ 的平衡的多级括号序列 $S$，我们称它的两个字符 $S_x,S_y$（$1 \le x < y \le k$）是对应括号当且仅当它们满足：$S_x$ 为左括号，且 $S_y$ 为右括号，且 $S_x$ 和 $S_y$ 为同级括号，且字符串 $S_{x+1},S_{x+2},\dots,S_{y-1}$ 是一个平衡的多级括号序列。

例如：假设 () 和 [] 表示两种不同级别的括号，则 ()([]) 是平衡的多级括号序列，且它的第 $1$ 个字符与第 $2$ 个字符、第 $3$ 个字符与第 $6$ 个字符、第 $4$ 个字符与第 $5$ 个字符分别对应，而 ([)] 不是一个平衡的多级括号序列。

我们称一个长度为 $k$ 的多级括号序列 $S$ 是可爱的，当且仅当它同时满足以下两种条件：

• $S$ 是一个平衡的多级括号序列。
• 对于任意一对对应括号 $S_x,S_y$（$1 \le x < y \le k$），假设它们的级别为 $v$，当 $v > 1$ 时，它们中间的子串 $S_{x+1},S_{x+2},\dots,S_{y-1}$ 只包含级别严格小于 $v$ 的括号且至少包含一个级别恰好为 $v-1$ 的括号；当 $v = 1$ 时，它们中间的子串是空串。

例如：假设 () 表示 $1$ 级括号，[] 表示 $2$ 级括号，{} 表示 $3$ 级括号，则 {[()]()}() 是一个可爱的多级括号序列，而 [(])、{()}、([]) 或 (()) 不是可爱的多级括号序列。

格式

输入格式

本题包含多组测试数据。

第一行包含两个非负整数 $c,t$，分别表示子任务编号与测试数据组数。$c=0$ 表示该测试点为样例。

对于每组测试数据，包含一行两个整数 $n,m$，含义请见题目描述。

输出格式

对于每组测试数据，包含一行一个整数，表示答案对 $998244353$ 取模的结果。

样例

样例输入 #1

0 3
3 2
2 2
2 1

样例输出 #1

5
3
1

样例解释 #1

假设 () 表示 $1$ 级括号，[] 表示 $2$ 级括号。

第一组测试数据中，满足条件的可爱的多级括号序列为：

()[()][()]

[()]()[()]

[()][()]()

[()()][()]

[()][()()]

第二组测试数据中，满足条件的可爱的多级括号序列为：

()[()]

[()()]

[()]()

第三组测试数据中，满足条件的可爱的多级括号序列为：

()()

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。子任务间有依赖关系，你只有通过某个子任务依赖的所有子任务，才会对该子任务进行评测。

子任务编号	分数	$n$	$m$	$\sum m \le$	子任务依赖
$1$	$10$	$\le 3$	$\le 3$	$3$	无
$2$	$20$	$\le 5$	$\le 5$	$5$	$1$
$3$	$6$	$<998244353$	$=1$	$2 \times 10^5$	无
$4$	$12$		$=2$
$5$	$15$	$\le 5000$	$\le 5000$	$5000$	$1,2$
$6$	$15$	$<998244353$			$1,2,5$
$7$	$22$		$\le 2 \times 10^5$	$2 \times 10^5$	$1,2,3,4,5,6$

对于 $100\%$ 的数据：$1 \le t,m,\sum m \le 2 \times 10^5$，$m \le n < 998244353$。