Fişierul intrare/ieşire:cntsubsirmax.in, cntsubsirmax.outSursăInfoPro, Runda 2, Grupa A
AutorTamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test0.2 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cntsubsirmax

Felicia este interesată de subşirul maxim lexicografic al unui şir de caractere. Reţineţi că un şir a este considerat mai mic în ordine lexicografică decât un şir $b$ dacă a este prefix al lui b, sau dacă există o poziţie i pentru care avem a[1] = b[1], ..., a[i - 1] = b[i - 1], şi a[i] < b[i]. Astfel, subşirul maxim lexicografic al unui şir de caractere este cel mai mare subşir, în ordinea lexicografică, al unui şir de caractere (de exemplu zzxx pentru azbxazbxaax). Pentru un şir s de caractere vom nota cu m(s) subşirul maxim lexicografic al lui s, şi cu v(s) = |m(s)| lungimea acestui subşir.

Felicia vă dă un şir s format din caractere mici ale alfabetului englez. Consideraţi toate subsecvenţele continue s' ale lui s. Felicia vrea să calculaţi suma valorilor v(s') pentru toate subsecvenţele posibile s' amintite anterior.

Date de intrare

Pe singura linie citită de la tastatură se va găsi şirul s.

Date de intrare

Să se afişeze suma cerută, modulo 1.000.000.007.

Restricţii

  • 1 ≤ |s| ≤ 1.000.000
  • Pentru 20 de puncte, |s| ≤ 15
  • Pentru alte 10 de puncte, |s| ≤ 200
  • Pentru alte 20 de puncte, |s| ≤ 2.000
  • Pentru alte 20 de puncte, |s| ≤ 10.000

Exemple

cntsubsirmax.incntsubsirmax.out
cab
8
felicia
59

Explicaţie

Pentru primul exemplu, observăm că m© = c, m(a) = a, m(b) = b, m(ca) = ca, m(ab) = b, m(cab) = cb. Astfel, răspunsul este 1 + 1 + 1 + 2 + 1 + 2 = 8.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?