How to solve this problem?

Revision en3, by Destopia, 2022-06-02 12:44:15

Given an array of $$$n \leq 10^5$$$ integers. $$$a_1, a_2, \dots a_n$$$. $$$f(i)$$$ is defined as follows:

  • Take the first $$$i$$$ elements $$$a_1, a_2, a_3, \dots a_i$$$, sort them in nondecreasing order. Let's call resulting prefix after sort $$$s$$$

  • Let $$$f(i) = 1 \times s_1 + 2 \times s_2 + 3 \times s_3 + \dots + i \times s_i$$$.

We're asked to calculate $$$f(1) + f(2) + \dots + f(n)$$$ $$$\bmod 10^9 + 7$$$.

Example $$$n = 4$$$ and array $$$[4, 3, 2, 1]$$$

$$$f(1) = 1 \times 4 = 4$$$

$$$f(2) = 1 \times 3 + 2 \times 4 = 11$$$,

$$$f(3) = 1 \times 2 + 2 \times 3 + 3 \times 4 = 20$$$

$$$f(4) = 1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 4 = 30$$$

$$$f(1) + f(2) + f(3) + f(4) = 4 + 11 + 20 + 30 = 65$$$.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Destopia 2022-06-02 12:44:15 2 Tiny change: ' \times s_4 + \dots +' -> ' \times s_3 + \dots +'
en2 English Destopia 2022-06-02 11:08:51 307
en1 English Destopia 2022-06-02 11:04:15 448 Initial revision (published)