A120390.数学题

Steve 在中考数学的考场上遇到了下面的题目：

——2024 年重庆中考数学（A 卷）

在解决了这道选择题之后，Steve 不禁开始思考：这道题目是不是还能加强？于是他出了下面的题目。

给定正整数 $S,k$，称关于 $x$ 的 $n$ 次整式 $P=a_0x^0+a_1x^1+\cdots+a_nx^n$ 为好的当且仅当：

• $a_0,a_1,\dots,a_{n-1}$ 均为非负整数，$a_n$ 为正整数。
• $n+a_0+a_1+\cdots+a_n=S$。

求好的关于 $x$ 的整式 $P$ 的个数 $X$，对 $998244353$ 取模，并输出第 $k$ 小的好的整式的次数 $Y$。注意你可以自由决定 $n$ 的值。

如果你不知道怎么比较两个关于 $x$ 的整式 $P,Q$ 的大小，可以参考这个定义：设 $P=p_0x^0+p_1x^1+\cdots+p_nx^n$，$Q=q_0x^0+q_1x^1+\cdots+q_mx^m$，约定当 $i>n$ 时 $p_i=0$，当 $i>m$ 时 $q_i=0$。令 $d$ 为满足 $p_d\not= q_d$ 的最大整数 $d$，若 $p_d<q_d$，则 $P<Q$；若 $p_d>q_d$，则 $P>Q$；若不存在这样的整数 $d$，则 $P=Q$。

每个测试点包含多组测试数据。输入的第一行包含两个正整数 $c,T$，分别表示测试点编号和测试数据的组数。对于每组测试数据：

第一行包含两个正整数 $S,k$，含义见题目描述。

对于每组测试数据，输出一行两个整数 $X,Y$，分别表示好的整式 $P$ 的个数对 $998244353$ 取模后的结果和第 $k$ 小的好的整式的次数。

【样例解释】

对于第一组测试数据，从小到大有 $4$，$x+2$，$2x+1$，$3x$，$x^2+1$，$x^2+x$，$2x^2$，$x^3$ 共 $8$ 个整式符合条件，其中第三小的整式为 $2x+1$，其次数为 $1$。

以 $P=x^2+1$ 为例，此时 $n=2,\ a_2=a_0=1,\ a_1=0$，符合 $n+\sum\limits_{i=0}^na_i=S$。

【数据范围】

测试点编号	特殊性质
$1-2$	$S\le 10,k=1$
$3$	$S\le 10$
$4$	$S\le 500,k=1$
$5$	$S\le 500$
$6$	$S\le 10^5,k=1$
$7$	$S\le 10^5$
$8-9$	$k\le 10^5$
$10$	无

对于 $100\%$ 的测试点，$1\le T\le100$，$1\le S,k\le10^9$，设好的多项式总数为 $C$，保证 $k\le C$。