Universal Cup Judging System

Universal Cup

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

令 $B$ 為一個長度為 $M$ 且由正整數組成的陣列。

在一次操作中,你可以選擇一個非空的下標子序列$^\dagger$ $1 \le i_1 < i_2 < \dots < i_k \le M$,使得對應的值 $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ 兩兩不同,然後將每個選定位置的值減 $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.