No.1300 Sum of Inversions
nok0
noya2
Kite_kumaProblem Statement
You are given a sequence $A$ of non-negative integers of length $N$. The $i$-th number is $A_i$.
For all tuples $(i, j, k)$ satisfying $i < j < k$ and $A_i > A_j > A_k$, find the sum of $A_i+A_j+A_k$.
Since the sum can be very large, output the remainder when it is divided by $998244353$.
Constraints
- All inputs are integers.
- $3 \le N\le 2 × 10^5$
- $0 \le A_i \le 10^9$
Input
$N$ $A_1\ A_2 \ \dots \ A_N$
Output
Output the remainder when the sum of $A_i+A_j+A_k$ over all tuples $(i, j, k)$ satisfying $i < j < k$ and $A_i > A_j > A_k$ is divided by $998244353$.
Sample
Sample 1
Input
3 3 2 1
Output
6
There is $1$ tuple $(i,j,k)$ satisfying the conditions: $(1,2,3)$. Since $A_1 + A_2 +A_3 = 6$, the answer is $6$.
Sample 2
Input
4 4 2 3 1
Output
15
There are $2$ tuples $(i,j,k)$ satisfying the conditions: $(1,2,4), (1,3,4)$. The values of $A_i+A_j+A_k$ are $7,8$ respectively, so the answer is $15$.
Sample 3
Input
10 3 1 4 1 5 9 2 6 5 3
Output
69
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。