Universal Cup Judging System

Universal Cup

Time Limit: 3.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

En heltalsföljd $V_1, V_2, \dots, V_N$ kallas superavtagande om $V_N \ge 0$ och $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$ för alla $1 \le i < N$.

Givet positiva heltal $N$ och $M$, bestäm antalet par av heltalsföljder $A$ och $B$ av längd $N$ sådana att $1 \le A_i, B_i \le M$ för alla $1 \le i \le N$, och det för alla superavtagande följder $V$ av längd $N$ gäller att

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

Eftersom antalet sådana par kan vara mycket stort, skriv ut svaret modulo $998\,244\,353$.

Indata

Indatan ges i följande format:

T
N M
:
  • Alla indatavärden är heltal.
  • $1 \le T \le 100$
  • $1 \le N, M \le 5000$
  • Det garanteras att summan av $N$ över alla testfall inte överstiger $5000$.
  • Det garanteras att summan av $M$ över alla testfall inte överstiger $5000$.

Utdata

För varje testfall, skriv ut ett enda heltal — antalet par av följder $(A, B)$ som uppfyller villkoren, modulo $998\,244\,353$.

Exempel

Exempelindata 1

4
1 1
2 2
2 1
34 43

Exempelutdata 1

1
10
1
711021868

Förklaring

Testfall 1: Det enda möjliga paret av följder är $([1], [1])$, och det är giltigt.

Testfall 2: Följande är giltiga par av följder:

  • För $B = [1, 1]$ är varje val av $A$ giltigt. Det finns $4$ möjliga val.
  • För $B = [1, 2]$ är giltiga val av $A$ lika med $[1, 2], [2, 1], [2, 2]$.
  • För $B = [2, 1]$ är giltiga val av $A$ lika med $[2, 1], [2, 2]$.
  • För $B = [2, 2]$ är det enda giltiga valet av $A$ lika med $[2, 2]$.

Alltså är antalet giltiga par av följder lika med $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.