Universal Cup Judging System

Universal Cup

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

設 $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.