| Fişierul intrare/ieşire: | w.in, w.out | Sursă | RMI 2018 |
| Autor | Zoltan Szabo | Adăugată de |  Laura Georgescu •laurageorgescu |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
W
Un vector de numere se spune că este de tip W dacă:
- Consistă din patru segmente în ordine descrescătoare, ordine crescătoare, ordine descrescătoare, ordine crescătoare.
- Ordinea nu este strictă, deci segmentele crescatoare şi descrescătoare pot include elementele consecutive egale.
- Oricare două segmente consecutive au un capăt comun.
- Orice segment conţine cel puţin două valori distincte.
De exemplu, vectorul (3 1 2 1 1 4) este de tip W, deoarece consistă din segmentele (3 1), (1 2), (2 1 1), (1 4). Vectorul (3 1 2 2 2 4) nu este de tip W. Acesta poate fi împărţit în segmentele (3 1), (1 2), (2 2 2), (2 4), dar segmentul (2 2 2) nu conţine cel puţin două valori distincte.
Dânduse un vector de N întregi, câte permutări distincte ale acestuia sunt de tip W? Două permutări (p1 p2 ... pN) şi (q1 q2 ... qN) se consideră distincte dacă exista o poziţie 1 ≤ i ≤ N astfel încât pi ≠ qi. In exemplul de mai sus, (3 1 2 1 1 4) trebuie numarată o singură dată, deoarece permutând cei 3 de 1 nu se creeaza permutări distincte.
Date de intrare
În fişierul de intrare w.in se află, pe prima linie, N. Pe a doua linie se găsesc cele N valori ale vectorului, separate prin spatii.
Date de ieşire
În fişierul de ieşire w.out se găseşte numărul de permutări distincte de tip W, modulo 1 000 000 007.
Restricţii
- 5 ≤ N ≤ 300 000
- Valorile elementelor din vector sunt numere naturale între 1 şi 1 000 000 inclusiv.
- Pentru 20% din teste, vectorul contine doar două valori distincte.
- Pentru alte 30% din teste, toate cele N elemente sunt distincte.
Exemplu
| w.in | w.out |
|---|---|
| 5 3 1 4 2 3 | 6 |
| 7 1 2 2 2 3 4 4 | 72 |
Explicaţii
Pentru primul exemplu, cele 6 permutari de tip W sunt:
3 1 3 2 4
3 1 4 2 3
3 2 3 1 4
3 2 4 1 3
4 1 3 2 3
4 2 3 1 3
