Universal Cup Judging System

Universal Cup

Süre Sınırı: 3.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

$B$ を正の整数からなる長さ $M$ の配列とします。

1 回の操作では、添字の空でない部分列$^\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$ からいくつか(0 個またはすべてでもよい)の要素を、残りの要素の順序を変えずに削除することで得られることをいいます。

入力

入力は以下の形式で与えられます:

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$ を超えないことが保証される。

出力

各テストケースについて、1 つの整数 — $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]$ に等しい 2 つの部分列(それぞれのスコアは $1$)、
  • $[3]$(スコアは $3$)、
  • $[1, 1]$(スコアは $2$)、
  • $[1, 3]$ に等しい 2 つの部分列(それぞれのスコアは $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.