Universal Cup Judging System

Universal Cup

実行時間制限: 3.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓
統計

Gọi $B$ là một mảng có độ dài $M$ gồm các số nguyên dương.

Trong một thao tác, bạn có thể chọn một dãy con khác rỗng$^\dagger$ các chỉ số $1 \le i_1 < i_2 < \dots < i_k \le M$ sao cho các giá trị $B_{i_1}, B_{i_2}, \dots, B_{i_k}$ đôi một phân biệt, rồi giảm mỗi giá trị được chọn đi $1$.

Định nghĩa điểm số của $B$, ký hiệu là $\text{score}(B)$, là số thao tác ít nhất cần thiết để biến mọi phần tử của $B$ thành $0$.

Bạn được cho một mảng $A$ có độ dài $N$.

Hãy tìm tổng điểm số trên tất cả các dãy con khác rỗng của $A$.

Vì giá trị này có thể rất lớn, hãy in ra kết quả theo modulo $998\,244\,353$.

$^\dagger$ Một dãy $C$ được gọi là một dãy con của dãy $D$ nếu có thể thu được nó từ $D$ bằng cách xóa một số phần tử (có thể không xóa phần tử nào hoặc xóa tất cả) mà không làm thay đổi thứ tự của các phần tử còn lại.

Dữ liệu vào

Dữ liệu vào được cho theo định dạng sau:

T
N
A_1 A_2 ... A_N
:
  • Tất cả các giá trị đầu vào đều là số nguyên.
  • $1 \le T \le 10^5$
  • $1 \le N \le 5000$
  • $1 \le A_i \le 10^9$
  • Dữ liệu đảm bảo tổng của $N^2$ trên tất cả các bộ test không vượt quá $5000^2$.

Kết quả

Với mỗi bộ test, in ra một số nguyên duy nhất — tổng điểm số trên tất cả các dãy con khác rỗng của $A$, theo modulo $998\,244\,353$.

Ví dụ

Ví dụ đầu vào 1

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

Ví dụ đầu ra 1

5
16
47

Ghi chú

Bộ test 1: Dãy con khác rỗng duy nhất là $[5]$, có điểm số là $5$. Do đó, đáp án là $5$.

Bộ test 2: Các dãy con khác rỗng của $[1, 1, 3]$ là:

  • hai dãy con bằng $[1]$, mỗi dãy có điểm số là $1$,
  • $[3]$, có điểm số là $3$,
  • $[1, 1]$, có điểm số là $2$,
  • hai dãy con bằng $[1, 3]$, mỗi dãy có điểm số là $3$,
  • $[1, 1, 3]$, có điểm số là $3$.

Vì vậy, tổng cộng là $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.