| Fişierul intrare/ieşire: | seqval.in, seqval.out | Sursă | Science On 2021, clasa 9 |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Todoran Alexandru Raul •alextodoran |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 268435 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Seqval
Pentru o secvenţă S = s1,...,sk de numere naturale distincte, fie i poziţia elementului maxim, şi j poziţia elementului minim. Definim v(S) = v(s1,...,sk) = i - j.
Se dă o permutare A = a1,...,aN a mulţimii {1,...,N}. Să se determine valoarea sumei:
![\[\sum_{1 \le i < j \le N} v(a_i,...,a_j)\]\hspace{1mm} mod 10^9+7](http://www.infoarena.ro/static/images/latex/94f5d400aabb7043cb0cf93471c95176_5.36115pt.gif "\[\sum_{1 \le i < j \le N} v(a_i,...,a_j)\]\hspace{1mm} mod 10^9+7")
Date de intrare
Primul rând al fişierului de intrare seqval.in conţine numărul natural N.
Al doilea rând conţine elementele permutării A in ordine.
Date de ieşire
Fişierul de ieşire seqval.out va conţine răspunsul, pe un singur rând.
Subtaskuri
Subtask 1 (20 puncte)
- N ≤ 200
Subtask 2 (20 puncte)
- N ≤ 2 000
Subtask 3 (40 puncte)
- N ≤ 200 000
Subtask 4 (20 puncte)
- N ≤ 500 000
Exemplu
| seqval.in | seqval.out |
|---|---|
| 5 1 2 3 4 5 | 20 |
| 3 2 3 1 | 1000000006 |
Explicaţie
Observăm că în primul exemplu suma cerută este:
v(1,2) + ... + v(4,5) + v(1,2,3) + ... + v(3,4,5) + v(1,2,3,4) + v(2,3,4,5) + v(1,2,3,4,5)
= 4×1 + 3×2 + 2×3 + 1×4
= 20
Observăm că în al doilea exemplu suma cerută este v(2,3) + v(3,1) + v(2,3,1) = (2 - 1) + (1 - 2) + (2 - 3) = -1, iar -1 mod 109 + 7 = 109 + 6.
