Universal Cup Judging System

Universal Cup

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

Sei $B$ ein Array der Länge $M$, das aus positiven ganzen Zahlen besteht.

In einer Operation darfst du eine nicht-leere Teilfolge$^\dagger$ von Indizes $1 \le i_1 < i_2 < \dots < i_k \le M$ wählen, sodass die Werte $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ paarweise verschieden sind, und anschließend jeden gewählten Wert um $1$ verringern.

Definiere den Score von $B$, bezeichnet mit $\text{score}(B)$, als die minimale Anzahl von Operationen, die benötigt werden, um jedes Element von $B$ gleich $0$ zu machen.

Gegeben ist ein Array $A$ der Länge $N$.

Bestimme die Summe der Scores über alle nicht-leeren Teilfolgen von $A$.

Da der Wert groß sein kann, gib ihn modulo $998\,244\,353$ aus.

$^\dagger$ Eine Folge $C$ heißt Teilfolge einer Folge $D$, wenn sie aus $D$ durch Löschen mehrerer Elemente (möglicherweise keiner oder aller) erhalten werden kann, ohne die Reihenfolge der verbleibenden Elemente zu ändern.

Eingabe

Die Eingabe erfolgt im folgenden Format:

T
N
A_1 A_2 ... A_N
:
  • Alle Eingabewerte sind ganze Zahlen.
  • $1 \le T \le 10^5$
  • $1 \le N \le 5000$
  • $1 \le A_i \le 10^9$
  • Es wird garantiert, dass die Summe von $N^2$ über alle Testfälle hinweg $5000^2$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzige ganze Zahl aus — die Summe der Scores über alle nicht-leeren Teilfolgen von $A$, modulo $998\,244\,353$.

Beispiele

Beispieleingabe 1

3
1
5
3
1 1 3
4
2 2 2 2

Beispielausgabe 1

5
16
47

Hinweis

Testfall 1: Die einzige nicht-leere Teilfolge ist $[5]$ mit Score $5$. Daher lautet die Antwort $5$.

Testfall 2: Die nicht-leeren Teilfolgen von $[1, 1, 3]$ sind:

  • zwei Teilfolgen gleich $[1]$, jeweils mit Score $1$,
  • $[3]$ mit Score $3$,
  • $[1, 1]$ mit Score $2$,
  • zwei Teilfolgen gleich $[1, 3]$, jeweils mit Score $3$,
  • $[1, 1, 3]$ mit Score $3$.

Also beträgt die Gesamtsumme $16$.

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.