Universal Cup Judging System

Universal Cup

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

$B$를 양의 정수로 이루어진 길이가 $M$인 배열이라고 합시다.

한 번의 연산에서, 대응하는 값 $B_{i_1}, B_{i_2}, \dots, B_{i_k}$가 서로 다른 인덱스의 비어 있지 않은 부분 수열$^\dagger$ $1 \le i_1 < i_2 < \dots < i_k \le M$을 선택한 뒤, 선택한 각 값을 $1$만큼 감소시킬 수 있습니다.

$B$의 점수 $\text{score}(B)$를 $B$의 모든 원소를 $0$으로 만들기 위해 필요한 최소 연산 횟수로 정의합니다.

길이가 $N$인 배열 $A$가 주어집니다.

$A$의 모든 비어 있지 않은 부분 수열에 대한 점수의 합을 구하세요.

값이 매우 클 수 있으므로, $998\,244\,353$으로 나눈 나머지를 출력하세요.

$^\dagger$ 수열 $C$가 수열 $D$에서 나머지 원소들의 순서를 바꾸지 않고 몇 개의 원소(하나도 삭제하지 않거나 모두 삭제할 수도 있음)를 삭제하여 얻을 수 있다면, 이를 $D$의 부분 수열이라고 부릅니다.

입력

입력은 다음 형식으로 주어집니다:

T
N
A_1 A_2 ... A_N
:
  • 모든 입력값은 정수입니다.
  • $1 \le T \le 10^5$
  • $1 \le N \le 5000$
  • $1 \le A_i \le 10^9$
  • 모든 테스트 케이스에서 $N^2$의 합은 $5000^2$을 초과하지 않음이 보장됩니다.

출력

각 테스트 케이스마다 $A$의 모든 비어 있지 않은 부분 수열에 대한 점수의 합을 $998\,244\,353$으로 나눈 나머지를 하나의 정수로 출력하세요.

예제

예제 입력 1

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

예제 출력 1

5
16
47

노트

테스트 케이스 1: 유일한 비어 있지 않은 부분 수열은 $[5]$이고, 점수는 $5$입니다. 따라서 답은 $5$입니다.

테스트 케이스 2: $[1, 1, 3]$의 비어 있지 않은 부분 수열은 다음과 같습니다:

  • $[1]$과 같은 부분 수열 두 개 (각각 점수 $1$),
  • $[3]$ (점수 $3$),
  • $[1, 1]$ (점수 $2$),
  • $[1, 3]$과 같은 부분 수열 두 개 (각각 점수 $3$),
  • $[1, 1, 3]$ (점수 $3$).

따라서 전체 합은 $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.