Fişierul intrare/ieşire:sdistante.in, sdistante.outSursăOJSEPI 2021, clasa a 10-a
AutorBogdan PopAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test0.3 secLimită de memorie64000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sdistante

Definim distanţa dintre două şiruri de caractere de aceeaşi lungime ca fiind numărul minim de caractere ce trebuie modificate (înlocuite fiecare cu câte un alt caracter) în primul şir pentru a obţine al doilea şir. Vom nota distanţa dintre şirurile a şi b cu dist(a, b).

De exemplu, dist(abc, aaa) = 2 (înlocuim caracterul b cu a, respectiv caracterul c cu a), iar dist(ABC, abc) = 3 (literele mici se consideră diferite de cele mari).

Definim o subsecvenţă a unui şir s de caractere ca fiind un şir format din caractere de pe poziţii consecutive din s. Considerăm două subsecvenţe ca fiind distincte dacă încep sau se termină la poziţii diferite. Vom nota cu s(i, j) subsecvenţa formată din caracterele indexate de la i la j ale şirului s. Şirurile se indexează de la 0. Exemplu: pentru şirul s = abc subsecvenţele sunt s(0, 0) = a, s(1,1) = b, s(2,2) = c, s(0,1) = ab, s(1,2) = bc, s(0,2) = abc, iar pentru şirul s= aa acestea sunt s(0,0) = a, s(1,1) = a, s(0,1) = aa.

Se dă un şir de caractere s, care poate conţine doar litere mici şi mari ale alfabetului englez (de la a la z şi de la A la Z). Pentru toate perechile neordonate de subsecvenţe distincte ale şirului s care au lungimi egale, vrem să calculăm distanţa dintre ele şi să afişăm suma acestora modulo 109 + 7. Formal, se cere suma valorilor dist(s(a, b), s(c, d)), pentru toţi indicii a, b, c, d cu 0 ≤ a, b, c, d < |s|, a < c, a ≤ b, c ≤ d, b-a = d-c, modulo 109 + 7. |s| reprezintă lungimea şirului s, care este indexat de la 0.

Date de intrare

Pe singura linie a fişierului sdistante.in este şirul dat, s.

Date de ieşire

Se va afişa pe singurul rând al fişierului sdistante.out un număr întreg reprezentând suma distanţelor, modulo 109 + 7.

Restricţii şi precizări

  • |s| ≤ 4.000.000, unde |s| este lungimea şirului s
  • Pentru 11 puncte |s| ≤ 20 şi s conţine doar litere mici.
  • Pentru alte 5 puncte |s| ≤ 50 şi s conţine doar caracterele a şi b.
  • Pentru alte 15 puncte |s| ≤ 350 şi s conţine doar litere mici.
  • Pentru alte 6 puncte |s| ≤ 1.000 şi s conţine doar caracterele a şi b.
  • Pentru alte 30 de puncte |s| ≤ 5.000 şi s conţine doar litere mici.
  • Pentru alte 5 puncte |s| ≤ 100.000 şi s conţine doar caracterele a şi b.
  • Pentru alte 4 puncte |s| ≤ 100.000 şi s conţine doar litere mici.
  • Pentru alte 6 puncte |s| ≤ 1.000.000 şi s conţine doar caracterele a şi b.
  • Atenţie! Este posibil ca punctajul să difere faţă de cel luat în concurs.

Exemple

sdistante.insdistante.out
abc5
aab3
ABa5
aaaaabbbaaaa480
abcdefghizabcdefghiz7095

Explicaţii

Pentru primul exemplu,

  • dist(s(0,0), s(1, 1)) = dist(a, b) = 1
  • dist(s(0,0), s(2, 2)) = dist(a, c) = 1
  • dist(s(1,1), s(2, 2)) = dist(b, c) = 1
  • dist(s(0,1), s(1, 2)) = dist(ab, bc) = 2

Pentru al doilea exemplu,

  • dist(s(0,0), s(1, 1)) = dist(a, a) = 0
  • dist(s(0,0), s(2, 2)) = dist(a, b) = 1
  • dist(s(1,1), s(2, 2)) = dist(a, b) = 1
  • dist(s(0,1), s(1, 2)) = dist(aa, ab) = 1

Pentru al treilea exemplu,

  • dist(s(0,0), s(1, 1)) = dist(A, B) = 1
  • dist(s(0,0), s(2, 2)) = dist(A, a) = 1
  • dist(s(1,1), s(2, 2)) = dist(B, a) = 1
  • dist(s(0,1), s(1, 2)) = dist(AB, Ba) = 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?