問題一覧 > 通常問題

No.1300 Sum of Inversions

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 195
作問者 : nok0nok0 / テスター : noya2noya2 Kite_kumaKite_kuma
34 ProblemId : 5438 / 出題時の順位表
問題文最終更新日: 2020-11-28 00:16:26

問題文

長さ $N$ の非負整数列 $A$ が与えられます。 $i$ 番目の数は $A_i$ です。

$i < j < k$ かつ $A_i > A_j > A_k$ を満たす全ての $(i, j, k)$ の組に対して、$A_i+A_j+A_k$ の総和を求めてください。

ただし総和はとても大きくなることがあるので、 $998244353$ で割った余りを答えてください。

制約

  • 入力は全て整数である。
  • $3 \le N\le 2 × 10^5$
  • $0 \le A_i \le 10^9$

入力

$N$
$A_1\ A_2 \ \dots \  A_N$

出力

$i < j < k$ かつ $A_i > A_j > A_k$ を満たす全ての $(i, j, k)$ の組に対して、$A_i+A_j+A_k$ の総和 を $998244353$ で割った余りを出力してください。

サンプル

サンプル1
入力
3
3 2 1
出力
6

条件を満たす $(i,j,k)$ の組は $(1,2,3)$ の $1$ つです。$A_1 + A_2 +A_3 = 6$ なので、答えは $6$ です。

サンプル2
入力
4
4 2 3 1
出力
15

条件を満たす $(i,j,k)$ の組は $(1,2,4), (1,3,4)$ の $2$ つです。$A_i+A_j+A_k$ は それぞれ $7,8$ なので、答えは $15$ です。

サンプル3
入力
10
3 1 4 1 5 9 2 6 5 3
出力
69

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。