Universal Cup Judging System

Universal Cup

実行時間制限: 3.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

Sebuah barisan bilangan bulat $V_1, V_2, \dots, V_N$ disebut super menurun (super decreasing) jika $V_N \ge 0$, dan $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ untuk semua $1 \le i < N$.

Diberikan bilangan bulat positif $N$ dan $M$, carilah banyaknya pasangan barisan bilangan bulat $A$ dan $B$ dengan panjang $N$ sedemikian sehingga $1 \le A_i, B_i \le M$ untuk semua $1 \le i \le N$, dan untuk semua barisan super menurun $V$ dengan panjang $N$, berlaku:

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

Karena banyaknya pasangan tersebut bisa sangat besar, cetak jawabannya modulo $998\,244\,353$.

Masukan

Masukan diberikan dalam format berikut:

T
N M
:
  • Semua nilai masukan adalah bilangan bulat.
  • $1 \le T \le 100$
  • $1 \le N, M \le 5000$
  • Dijamin bahwa jumlah $N$ di seluruh kasus uji tidak melebihi $5000$.
  • Dijamin bahwa jumlah $M$ di seluruh kasus uji tidak melebihi $5000$.

Keluaran

Untuk setiap kasus uji, keluarkan satu bilangan bulat — banyaknya pasangan barisan $(A, B)$ yang memenuhi kondisi, modulo $998\,244\,353$.

Contoh

Contoh Masukan 1

4
1 1
2 2
2 1
34 43

Contoh Keluaran 1

1
10
1
711021868

Catatan

Kasus uji 1: Satu-satunya pasangan barisan yang mungkin adalah $([1], [1])$, dan pasangan ini valid.

Kasus uji 2: Berikut adalah pasangan-pasangan barisan yang valid:

  • Untuk $B = [1, 1]$, pilihan $A$ mana pun valid. Terdapat $4$ pilihan yang mungkin.
  • Untuk $B = [1, 2]$, pilihan $A$ yang valid adalah $[1, 2], [2, 1], [2, 2]$.
  • Untuk $B = [2, 1]$, pilihan $A$ yang valid adalah $[2, 1], [2, 2]$.
  • Untuk $B = [2, 2]$, satu-satunya pilihan $A$ yang valid adalah $[2, 2]$.

Jadi, banyaknya pasangan barisan yang valid sama dengan $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.