Контест Middle Производительность и кеш обновлено
Различные подстроки длины k без лишних аллокаций
Условие
Строка длины L из первых σ строчных латинских букв генерируется так: x₀ = seed, x_{i+1} = (x_i · 1103515245 + 12345) mod 2³¹, символ номер i равен букве 'a' + ((x_{i+1} >> 16) mod σ). Посчитайте количество различных подстрок длины k.
Ввод: L, k, σ, seed (1 ≤ k ≤ L ≤ 10⁶, k ≤ 12, 1 ≤ σ ≤ 26, 0 ≤ seed < 2³¹).
Вывод: количество различных подстрок длины k.
Ограничение по времени 2 секунды.
Пример 1
Ввод:
10 3 2 1
Вывод:
7
Пример 2
Ввод:
1 1 1 0
Вывод:
1
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.