| Fişierul intrare/ieşire: | enigma.in, enigma.out | Sursă | Lot Sibiu 2011 |
| Autor | Andrei Parvu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.225 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Enigma
Green şi Riemann sunt doi prieteni buni cărora le place să joace un joc numit “enigma”. În acest joc, unul dintre ei scrie un cuvânt format din N caractere, iar celalalt vine cu M cuvinte de maxim S caractere. Scopul celui de-al doilea jucător este să îşi dea seama în câte moduri poate primul cuvânt să fie format din concatenarea prefixelor unor cuvinte dintre cele M.
Dacă s-a găsit un mod de a forma primul cuvânt, atunci fiecare poziţie i a acestuia va avea asociată o pereche (x, y), semnificând faptul că poziţia i este acoperită de al y-lea caracter din cuvântul x. Astfel, două moduri de a forma primul cuvânt sunt considerate diferite dacă există două poziţii i şi j, cu perechile asociate (x1, y1) şi (x2, y2) astfel încât x1 != x2 sau y1 != y2 .
Realizaţi un program care să rezolve jocul “enigma”!
Date de intrare
Fişierul de intrare enigma.in va conţine pe prima linie două numere N şi M cu semnificaţia din enunţ. A doua linie va conţine primul cuvânt format din N caractere. Urmează M linii, fiecare conţinând un cuvânt de maxim S caractere.
Date de ieşire
Fişierul de ieşire enigma.out va conţine pe prima linie numărul de moduri în care primul cuvant poate fi obţinut din concatenarea prefixelor unor cuvinte dintre cele M, modulo 31333 .
Restricţii
- 1 ≤ N ≤ 300 000
- 1 ≤ M ≤ 4 500
- 1 ≤ S ≤ 100
- un caracter este definit ca fiind o literă mică din alfabetul englez
- un cuvânt poate apărea de mai multe ori
- prefixele cuvintelor pot fi doar concatenate, nu şi suprapuse
Exemplu
| enigma.in | enigma.out |
|---|---|
| 7 3 xxxabdc xxx abdc c | 8 |
Explicaţie
Considerând numerotarea cuvintelor cea din fişierul de intare, perechile asociate poziţiilor primului cuvânt sunt:
1. (1, 1) (1, 1) (1, 1) (2, 1) (2, 2) (2, 3) (2, 4);
2. (1, 1) (1, 2) (1, 1) (2, 1) (2, 2) (2, 3) (2, 4);
3. (1, 1) (1, 1) (1, 2) (2, 1) (2, 2) (2, 3) (2, 4);
4. (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (2, 4);
5. (1, 1) (1, 1) (1, 1) (2, 1) (2, 2) (2, 3) (3, 1);
6. (1, 1) (1, 2) (1, 1) (2, 1) (2, 2) (2, 3) (3, 1);
7. (1, 1) (1, 1) (1, 2) (2, 1) (2, 2) (2, 3) (3, 1);
8. (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1);
