[R16E]数组问题 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定整数 $n$ 和 $m$，求有多少个长度为 $n$ 的整数数组 $a$ 同时满足以下两个条件：

• $\sum_{i=1}^n a_i=m$；
• $a_1\geq 1$，且对于 $2\leq i\leq n$，有 $a_i\geq a_{i-1}$。

答案对 $998244353$ 取模。

共有 $T$ 组数据。

格式

输入格式

第一行包含一个整数 $T$，表示数据的组数。

对于每组数据：

第一行包含两个整数 $n,m$，含义与题目描述相同。

输出格式

对于每组数据，在单独的一行中输出一个整数，表示满足条件的整数数组 $a$ 的数量。对 $998244353$ 取模。

样例

样例输入 #1

2
2 6
5 10

样例输出 #1

3
7

样例解释 #1

对于第 $1$ 组数据，满足条件的整数数组 $a$ 有 $3$ 个：$\{1,5\}$，$\{2,4\}$，$\{3,3\}$。

对于第 $2$ 组数据，满足条件的整数数组 $a$ 有 $7$ 个：$\{1,1,1,1,6\}$，$\{1,1,1,2,5\}$，$\{1,1,1,3,4\}$，$\{1,1,2,2,4\}$，$\{1,1,2,3,3\}$，$\{1,2,2,2,3\}$，$\{2,2,2,2,2\}$。

样例输入 #2

2
5000 5000
1234 4321

样例输出 #2

1
4533054

数据规模

对于 $40\%$ 的数据，$n\leq m\leq 100$。

对于 $80\%$ 的数据，$n\leq m\leq 2000$。

对于 $100\%$ 的数据，$1\leq T\leq 10^5$，$1\leq n\leq m\leq 8000$。