Fişierul intrare/ieşire:codificare.in, codificare.outSursăTabăra ICHB 2012, Ziua 1, Grupa 1
AutorDan Constantin SpatarelAdăugată despatarelDan-Constantin Spatarel spatarel
Timp execuţie pe test0.075 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Codificare

În ultima misiune în care a participat, Birkhoff a trebuit să spargă sistemul de telecomunicaţii radio al infractorilor - ceva banal pentru el, desigur. Acum, că misiunea s-a terminat cu succes, Birkhoff ştie codul de criptare folosit de inamici şi îl studiază, pentru a-şi putea scrie raportul misiunii.

Codul de criptare este un şir C de lungime N format din caractere mici ale alfabetului englez. Birkhoff se întreabă în câte moduri se poate obţine şirul C pornind de la un subşir S al său de lungime 1, folosind succesiv următoarele operaţii:

  • prefixează şirul S cu un caracter;
  • sufixează şirul S cu un caracter.

În timp ce voi citeaţi problema, Birkhoff s-a apucat deja să-şi scrie raportul. Dacă vreţi să ajungeţi şi voi într-o bună zi ca el, va trebui să răspundeţi la întrebarea sa pentru orice subşir S.

Date de intrare

Fişierul de intrare codificare.in conţine pe prima linie numărul natural N şi pe a doua linie şirul de caractere C.

Date de ieşire

În fişierul de ieşire codificare.out se va găsi pe prima linie numărul natural K reprezentând numărul de subşiruri distincte de lungime 1 ale şirului C.

Pe fiecare din următoarele K linii se vor regăsi, separate printr-un spaţiu, un subşir S şi numărul de moduri de a ajunge de la acesta la şirul C modulo 666013. Cele K linii vor fi sortate lexicografic.

Restricţii

  • 1 N 100 000
  • Pentru 25% din teste se garantează că N ≤ 20.
  • Pentru 50% din teste se garantează că N ≤ 1 000.

Exemplu

codificare.incodificare.out
3
aba
2
a 2
b 2

Explicaţie

Subşirurile distincte S sunt a şi b. Pentru fiecare există câte două modalităţi prin care se poate obţine şirul C:

  • a -> ab -> aba
  • a -> ba -> aba
  • b -> ba -> aba
  • b -> ab -> aba
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?