3889 - Cnt Subsir Max
Cerinţa[edit]
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[edit]
Pe singura linie citită de la tastatură se va găsi șirul s.
Date de ieșire[edit]
Să se afișeze suma cerută, modulo 109+7.
Restricţii şi precizări[edit]
- 1≤N≤106
Subtask[edit]
- N≤15
Subtask[edit]
- N≤200
Subtask[edit]
- N≤2000
Subtask[edit]
- N≤5⋅104
Subtask[edit]
- Fară restricții suplimentare.
Exemplul 1[edit]
- Intrare
cab
- Ieșire
8
Explicație[edit]
Pentru primul exemplu, observăm că m(c) = 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.
Exemplu 2[edit]
- Intrare
felicia
- Ieșire
59
Rezolvare[edit]
<syntaxhighlight lang="python" line> MOD = 10**9 + 7
def max_lexicographic(s):
max_substring = s[0]
for i in range(1, len(s)):
if s[i] >= max_substring[0]:
max_substring = s[i] + max_substring
else:
max_substring += s[i]
return max_substring
def sum_of_max_substrings(s):
total_sum = 0
for i in range(len(s)):
max_substring = max_lexicographic(s[i:])
total_sum += len(max_substring)
total_sum %= MOD
return total_sum
def main():
s = input().strip() result = sum_of_max_substrings(s) print(result)
if __name__ == "__main__":
main()
</syntaxhighlight>