No.1300 Sum of Inversions
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 240
作問者 :
nok0
/ テスター :
noya2
Kite_kuma
タグ : / 解いたユーザー数 240
作問者 :
nok0
/ テスター :
noya2
Kite_kuma
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。