G1 - Genuine Multiple Dependencies [Easy]

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo

問題 G2 とは制約のみが異なります

問題文

非負整数 nn と 正整数 xx についての関数 fn(x)f_n(x) を次のように定めます.

fn(x){1ifn=0k=1xfn1(k)ifn1f_n(x) \coloneqq \begin{dcases} \hspace{0.02em} 1 & \mathrm{if} \hspace{0.5em} n = 0 \\ \hspace{0.02em} \sum^{x}_{k=1} f_{n-1}(k) & \mathrm{if} \hspace{0.5em} n \geq 1 \end{dcases}

TT 個のテストケースが与えられます.
t(1tT)t \scriptsize \hspace{0.3em} (1 \leq t \leq T) 個目のテストケースでは,N=Nt,X=XtN = N_t,\,X = X_t として下記の問題を解いてください.

  • 非負整数 NN と正整数 XX について, fN(X)f_N(X) の値を 998244353998244353 で割ったあまりを求めてください.

制約

  • 1T5001 \leq T \leq 500
  • 0N3000 \leq N \leq 300
  • 1X3001 \leq X \leq 300
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる.

TT
N1X1N_1 \hspace{0.5em} X_1
N2X2N_2 \hspace{0.5em} X_2
\vdots
NTXTN_T \hspace{0.5em} X_T

出力

TT 行出力せよ.
t(1tT)t \scriptsize \hspace{0.3em} (1 \leq t \leq T) 行目には tt 個目のテストケースに対する答えを出力せよ.

注意

Python で解答しようとしている方へ: CPython はループが遅く,PyPy は再帰が遅いとされています.TLE には十分に注意してください.

サンプル

この問題には ビジュアライザ(Desmos) があります

入力例1
11
0 1
1 1
1 3
2 6
2 10
6 8
5 14
12 7
14 21
0 300
300 1
出力例1
1
1
3
21
55
1716
8568
18564
393731287
1
1

たとえば,

f0(1)=1f1(3)=k=13f0(k)=f0(1)+f0(2)+f0(3)=3f2(6)=k=16f1(k)=f1(1)+f1(2)++f1(6)=21\begin{darray}{ll} f_0(1) = 1 \\ f_1(3) = \sum^3_{k=1} f_0(k) = f_0(1) + f_0(2) + f_0(3) = 3 \\ f_2(6) = \sum^6_{k=1} f_1(k) = f_1(1) + f_1(2) + \cdots + f_1(6) = 21 \end{darray}

などが成り立ちます.

998244353998244353 で割ったあまりを出力することを忘れないようにしてください.

Submit


Go (1.21)