7/21/2019 Reverse z

1/1

Tabra de pregtire a lotului naional de informatic R mnicu V lcea, 24 aprilie - 1 mai 2015 Baraj 2 SenioriSursa: reversez .c / reversez .cpp / reversez .pas

pag. 1/1

Problema 2 reversez 100 puncte

Considerm un alfabet cuSigma caractere. Notam lcp(S, P)= cel mai lung prefix comun dintre un string S i un

string P . Pentru un string S o s notmSuffixS[i] = sufixul stringului S care ncepe la poziia i. Avnd stringul S ,o s crem irulA[i] = lcp(S, SuffixS[i]) .

CerinCunoscnd irulA i lungimea alfabetuluiSigma , s determine cte stringuriS genereaz sirulA.

Date de intrare

Pe prima linie a fiierului de intrarereversez.in se vor afla doua numere naturale N i Sigma , cu semnificaiadin enun.Pe linia 2 se vor afla N numere naturale reprezentnd irul A.

Date de ieire

n fiierul de ieirereversez.out vei afia un singur numr natural reprezentnd numrul de stringuriS cerut,modulo 666013 .

Restricii si precizri 1 N 3 00 000 1 Sigma 100 000 Numrul de soluii va fi cel puin 1.

Exemplu

reversez.in reversez.out Explicaie 4 34 1 0 1

6 Dac Sigma= {1,2,3}, cele 6 stringuri S posibile sunt:112111312212223233133323

Limit d e timp: 0.5 secunde/test.Memorie total disponibil: 128 MB , din care 64 MB pentru stiv Dimensiunea maxim a sursei: 20 KB