Fişierul intrare/ieşire:reversez.in, reversez.outSursăLot Râmnicu Vâlcea 2015 - Baraj 2 Seniori
AutorEugenie Daniel PosdarascuAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test0.2 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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.inreversez.outExplicatie
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

Cum se trimit solutii?