No.1733 Sum of Sorted Subarrays
タグ : / 解いたユーザー数 37
作問者 :
torisasami4
/ テスター :
tokusakurai
sapphire__15
Problem Statement
You are given a sequence $A=(A_0,A_1,\dots,A_{N-1})$ consisting of $N$ positive integers.
For a pair of integers $(l,r)$ satisfying $0 \le l \le r \lt N$, define $f(l,r)$ as follows.
Let $B=(B_0,B_1,\dots,B_{r-l})$ be the sequence obtained by sorting the sequence $(A_l,A_{l+1},\dots,A_r)$ in ascending order.
Then $f(l,r)=\displaystyle \sum_{i=0}^{r-l} (B_i\times2^i)$.
Find the value of $\displaystyle \sum_{l=0}^{N-1} \sum_{r=l}^{N-1} f(l,r)$, modulo $998244353$.
Input
$N$
$A_0\ A_1\ \ldots\ A_{N-1}$
[Constraints]
$1 \le N \le 2\times10^5$
$1 \le A_i \le 10^8$
All input values are integers.
Output
Output the answer $\textrm{mod}\ 998244353$.
Sample
Sample 1
Input
4
2 4 1 3
Output
129
For example, when $(l,r)=(1,3)$, we have $B=(1,3,4)$, so
$f(1,3)=1\times2^0+3\times2^1+4\times2^2=23$.
Sample 2
Input
2
1 1
Output
5
Sample 3
Input
8
61470509 48973000 57422921 44922273 1822769 55837022 9419711 41200362
Output
280998770
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。