| Fişierul intrare/ieşire: | deceeu.in, deceeu.out | Sursă | ACM ICPC Faza Nationala 2015 |
| Autor | Din Folclor | Adăugată de |  Comisie ICPC UPB •neapuiu |
| Timp execuţie pe test | 0.6 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
De ce eu?
PCP tocmai a primit, de la serviciile secrete, un şir de N caractere mici ale alfabetului englez. Acesta trebuie să afle câte subşiruri ale şirului dat sunt perfecte.
Un şir de caractere se numeste perfect dacă poate fi format concatenând două copii ale aceluiaşi şir. Spre exemplu, ”mama” (”ma” + ”ma”) sau ”abcabc” (”abc” + ”abc”) sunt şiruri perfecte, pe când ”pap” sau ”abcd” nu sunt. Un şir X este considerat subşir al şirului Y dacă X poate fi format prin ştergerea a zero sau mai mai multe caractere din Y.
Când a citit problema, PCP a fost foarte descurajat, întrebându-se ”De ce am primit eu cerinţa aceasta?”. Voi trebuie să-i arataţi că încă există speranţă şi să-l ajutaţi cu rezolvarea!
Date de intrare
Fişierul de intrare deceeu.in conţine pe prima linie T, numărul de teste. Urmează T linii, fiecare linie descriind un test şi fiind formată dintr-un şir de caractere de dimensiune N.
Date de ieşire
Fişierul de ieşire deceeu.out trebuie să conţină T linii. Cea de-a i-a linie reprezintă răspunsul pentru testul i din fişiserul de intrare. Deoarece răspunsul poate fi foarte mare, afisaţi-l modulo 1.000.000.007.
Restricţii
- 1 ≤ N ≤ 200
- 1 ≤ T ≤ 20
Exemplu
| deceeu.in | deceeu.out |
|---|---|
| 5 abc abca effeef bbbb aabbbaaabababbabbaab | 0 1 10 7 25545 |
Explicaţie
Subşirurile sunt descrise prin poziţiile din şirul iniţial care le formează.
Pentru testul 3, cele 10 subşiruri sunt: {1, 4}, {1, 5}, {4, 5}, {1, 2, 4, 6}, {1, 2, 5, 6}, {1, 3, 4, 6}, {1, 3, 5, 6}, {2, 3}, {2, 6}, {3, 6}.
Pentru testul 4, cele 7 subşiruri sunt: {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3, 4}.
