Universal Cup Judging System

Universal Cup

시간 제한: 3.0 s 메모리 제한: 1024 MB 총점: 100 해킹 가능 ✓
통계

整数列 $V_1, V_2, \dots, V_N$ は、$V_N \ge 0$ であり、かつすべての $1 \le i < N$ に対して $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ を満たすとき、超減少(super decreasing)であると呼ばれます。

正の整数 $N$ と $M$ が与えられます。長さ $N$ の整数列 $A$ と $B$ の組であって、すべての $1 \le i \le N$ に対して $1 \le A_i, B_i \le M$ を満たし、さらに長さ $N$ のすべての超減少数列 $V$ に対して

$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i.$$

が成り立つものの個数を求めてください。このような組の個数は非常に大きくなる可能性があるため、答えを $998\,244\,353$ で割った余りを出力してください。

入力

入力は以下の形式で与えられます:

T
N M
:
  • 入力される値はすべて整数である。
  • $1 \le T \le 100$
  • $1 \le N, M \le 5000$
  • すべてのテストケースにおける $N$ の総和は $5000$ を超えないことが保証される。
  • すべてのテストケースにおける $M$ の総和は $5000$ を超えないことが保証される。

出力

各テストケースについて、条件を満たす数列の組 $(A, B)$ の個数を $998\,244\,353$ で割った余りを表す整数を 1 つ出力してください。

入出力例

入力例 1

4
1 1
2 2
2 1
34 43

出力例 1

1
10
1
711021868

注記

テストケース 1: あり得る唯一の数列の組は $([1], [1])$ であり、これは条件を満たします。

テストケース 2: 条件を満たす数列の組は以下の通りです:

  • $B = [1, 1]$ のとき、$A$ はどのように選んでも条件を満たします。選び方は $4$ 通りあります。
  • $B = [1, 2]$ のとき、条件を満たす $A$ の選び方は $[1, 2], [2, 1], [2, 2]$ です。
  • $B = [2, 1]$ のとき、条件を満たす $A$ の選び方は $[2, 1], [2, 2]$ です。
  • $B = [2, 2]$ のとき、条件を満たす唯一の $A$ の選び方は $[2, 2]$ です。

したがって、条件を満たす数列の組の個数は $4 + 3 + 2 + 1 = 10$ です。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.