Atenţie! Aceasta este ultima versiune a paginii, scrisă la 2015-05-15 16:43:54.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | reversez.in, reversez.out | Sursă | Lot Râmnicu Vâlcea 2015 - Baraj 2 Seniori |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Tatomir Alex •atatomir |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Reversez
Considerăm un alfabet cu Sigma caractere. Notam lcp(S, P) = cel mai lung prefix comun dintre un string S şi un string P. Pentru un string S o să notăm SuffixS[i] = sufixul stringului S care începe la poziţia i. Având stringul S, o să creăm şirul A[i] = lcp(S, SuffixS[i]).
Cerinta
Cunoscând şirul A şi lungimea alfabetului Sigma, să determine câte stringuri S generează sirul A.
Date de intrare
Pe prima linie a fişierului de intrare reversez.in se vor afla doua numere naturale N şi Sigma, cu semnificaţia din enunţ.
Pe linia 2 se vor afla N numere naturale reprezentând şirul A.
Date de ieşire
În fişierul de ieşire reversez.out veţi afişa un singur număr natural reprezentând numărul de stringuri S cerut, modulo 666013.
Restricţii
- 1 ≤ N ≤ 300 000
- 1 ≤ Sigma ≤ 100 000
- Numărul de soluţii va fi cel puţin 1.
Exemplu
| reversez.in | reversez.out | Explicatie |
|---|---|---|
| 4 3 4 1 0 1 | 6 | Dacă Sigma={1,2,3}, cele 6 stringuri S posibile sunt: 1121 1131 2212 2232 3313 3323 |
Trebuie sa te autentifici pentru a trimite solutii. Click aici
