Войти Регистрация
Алгоритмы

181. Строки, где MTS переживает любые разрезы

Сложная

Строка из заглавных латинских букв — MTS-строка, если из неё можно вычеркнуть буквы и получить MTS. Строка k-устойчивая, если при любом разрезании на k подряд идущих частей (части могут быть пустыми) хотя бы одна часть — MTS-строка.

Верните число k-устойчивых строк длины n по модулю 998244353.

Задача из финала чемпионата МТС True Tech Champ 2024 — олимпиадная, не с собеседования.

В работе: Устойчивость метки к нарезке: сколько вариантов текста сохранят подпись, как бы его ни разбили на k сообщений.

Пример 1

Ввод
n = 3
k = 1
Вывод
1

Подходит только сама строка MTS.

Пример 2

Ввод
n = 6
k = 2
Вывод
1

Нужно две непересекающиеся MTS подряд, например MTSMTS.

Ограничения

  • 1 ≤ n, k ≤ 3·10⁴
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def resistant_count(n, k):
КомбинаторикаЖадный алгоритмОстаток от деленияцельO(n)

Источник: МТС, чемпионат True Tech Champ 2024, разбор в блоге компании на Хабре. Условие пересказано своими словами.