問題一覧 > 通常問題

No.1733 Sum of Sorted Subarrays

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 : torisasami4torisasami4 / テスター : sapphire__15sapphire__15 tokusakuraitokusakurai
2 ProblemId : 7201 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-04 03:28:16

問題文

$N$ 個の正整数からなる数列 $A=(A_0,A_1,\dots,A_{N-1})$ が与えられます。

$0 \le l \le r \lt N$ を満たす整数組 $(l,r)$ について、$f(l,r)$を以下のように定義します。

  数列 $(A_l,A_{l+1},\dots,A_r)$ を昇順に並べ替えたものを $B=(B_0,B_1,\dots,B_{r-l})$ として、
  $f(l,r)=\displaystyle \sum_{i=0}^{r-l} (B_i\times2^i)$ とする。

$\displaystyle \sum_{l=0}^{N-1} \sum_{r=l}^{N-1} f(l,r)$ の値を $998244353$ で割った余りを求めてください。

入力

$N$
$A_0\ A_1\ \ldots\ A_{N-1}$

【制約】

  • $1 \le N \le 2\times10^5$

  • $1 \le A_i \le 10^8$

  • 入力は全て整数

出力

答えを $\textrm{mod}\ 998244353$ で出力してください。

サンプル

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

例えば、$(l,r)=(1,3)$ のとき、$B=(1,3,4)$ となるため、

$f(1,3)=1\times2^0+3\times2^1+4\times2^2=23$ です。

サンプル2
入力
2
1 1
出力
5

サンプル3
入力
8
61470509 48973000 57422921 44922273 1822769 55837022 9419711 41200362
出力
280998770

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