Revizia anterioară Revizia următoare
| 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/b6f9684b39e32501c6500008187deac8_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 &le 200
Subtask 2 (20 puncte)
- N &le 2 000
Subtask 3 (40 puncte)
- N &le 200 000
Subtask 4 (20 puncte)
- N &le 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 10{9} + 7 = 10{9}+6.
