Universal Cup Judging System

Universal Cup

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

Soit $B$ un tableau de longueur $M$ composé d'entiers strictement positifs.

En une opération, vous pouvez choisir une sous-séquence non vide$^\dagger$ d'indices $1 \le i_1 < i_2 < \dots < i_k \le M$ telle que les valeurs $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ soient deux à deux distinctes, puis diminuer chaque valeur choisie de $1$.

On définit le score de $B$, noté $\text{score}(B)$, comme le nombre minimal d'opérations nécessaires pour rendre chaque élément de $B$ égal à $0$.

On vous donne un tableau $A$ de longueur $N$.

Trouvez la somme des scores sur toutes les sous-séquences non vides de $A$.

Comme cette valeur peut être grande, affichez-la modulo $998\,244\,353$.

$^\dagger$ Une séquence $C$ est appelée sous-séquence d'une séquence $D$ si elle peut être obtenue à partir de $D$ en supprimant plusieurs éléments, éventuellement aucun ou tous, sans changer l'ordre des éléments restants.

Entrée

L'entrée est donnée dans le format suivant :

T
N
A_1 A_2 ... A_N
:
  • Toutes les valeurs d'entrée sont des entiers.
  • $1 \le T \le 10^5$
  • $1 \le N \le 5000$
  • $1 \le A_i \le 10^9$
  • Il est garanti que la somme des $N^2$ sur l'ensemble des cas de test ne dépasse pas $5000^2$.

Sortie

Pour chaque cas de test, affichez un seul entier — la somme des scores sur toutes les sous-séquences non vides de $A$, modulo $998\,244\,353$.

Exemples

Exemple d'entrée 1

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

Exemple de sortie 1

5
16
47

Note

Cas de test 1 : La seule sous-séquence non vide est $[5]$, de score $5$. Par conséquent, la réponse est $5$.

Cas de test 2 : Les sous-séquences non vides de $[1, 1, 3]$ sont :

  • deux sous-séquences égales à $[1]$, chacune de score $1$,
  • $[3]$, de score $3$,
  • $[1, 1]$, de score $2$,
  • deux sous-séquences égales à $[1, 3]$, chacune de score $3$,
  • $[1, 1, 3]$, de score $3$.

Ainsi, la somme totale vaut $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.