Universal Cup Judging System

Universal Cup

Limite de temps : 3.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

Eine ganzzahlige Folge $V_1, V_2, \dots, V_N$ heißt superfallend, wenn $V_N \ge 0$ ist und für alle $1 \le i < N$ die Ungleichung $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ gilt.

Gegeben sind positive ganze Zahlen $N$ und $M$. Bestimme die Anzahl der Paare ganzzahliger Folgen $A$ und $B$ der Länge $N$, sodass $1 \le A_i, B_i \le M$ für alle $1 \le i \le N$ gilt und für alle superfallenden Folgen $V$ der Länge $N$

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

Da die Anzahl solcher Paare sehr groß sein kann, gib die Antwort modulo $998\,244\,353$ aus.

Eingabe

Die Eingabe erfolgt im folgenden Format:

T
N M
:
  • Alle Eingabewerte sind ganze Zahlen.
  • $1 \le T \le 100$
  • $1 \le N, M \le 5000$
  • Es wird garantiert, dass die Summe von $N$ über alle Testfälle hinweg $5000$ nicht überschreitet.
  • Es wird garantiert, dass die Summe von $M$ über alle Testfälle hinweg $5000$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzige ganze Zahl aus — die Anzahl der Folgenpaare $(A, B)$, die die Bedingungen erfüllen, modulo $998\,244\,353$.

Beispiele

Beispieleingabe 1

4
1 1
2 2
2 1
34 43

Beispielausgabe 1

1
10
1
711021868

Hinweis

Testfall 1: Das einzige mögliche Folgenpaar ist $([1], [1])$, und es ist gültig.

Testfall 2: Die folgenden Folgenpaare sind gültig:

  • Für $B = [1, 1]$ ist jede Wahl von $A$ gültig. Es gibt $4$ mögliche Wahlen.
  • Für $B = [1, 2]$ sind die gültigen Wahlen für $A$ gleich $[1, 2], [2, 1], [2, 2]$.
  • Für $B = [2, 1]$ sind die gültigen Wahlen für $A$ gleich $[2, 1], [2, 2]$.
  • Für $B = [2, 2]$ ist die einzige gültige Wahl für $A$ gleich $[2, 2]$.

Somit beträgt die Anzahl der gültigen Folgenpaare $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.