Задачник Базовый курс EN

ДНК без участка рестрикции

подсчёт вариантов поиск в тексте автомат матрица разделяй и властвуй биоинформатика олимпиады

Фермент рестрикции режет ДНК там, где встречает свой участок узнавания — короткое слово из букв A, C, G, T: EcoRI режет на GAATTC, BamHI — на GGATCC. Сколько существует последовательностей ДНК длины n, в которых участок не встречается ни разу и которые фермент поэтому не тронет? Последовательности — любые слова из букв A, C, G, T; ответ выведите по модулю 10⁹ + 7.

Во втором примере — участок EcoRI и длина генома фага лямбда, 48 502 буквы (NCBI RefSeq NC_001416.1).

Вход

Одна строка: n и слово w (1 ≤ n ≤ 10¹⁸, 1 ≤ |w| ≤ 15, w состоит из букв A, C, G, T).

Выход

Число последовательностей длины n, в которых w не встречается как подряд идущий кусок, по модулю 10⁹ + 7.

Примеры

Пример 1

Вход

3 AA

Выход

Пример 2

Вход

48502 GAATTC

Выход

394153108

Ограничения

Время · Python: 4000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 10 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Представьте, что последовательность пишут по букве и после каждой буквы смотрят: какой самый длинный кусок начала слова сейчас дописан в конце? Сколько возможных ответов на этот вопрос и что меняет следующая буква?

2Подсказка 2

Для слова AAC и текста …AAA: после третьей A дописано не «ничего», а снова AA. Правило «не совпало — вернись в начало» здесь ошибается.

3Идея

Состояние — сколько букв слова совпало с концом написанного текста: от 0 до |w| − 1 (дойти до |w| нельзя — это значило бы, что слово встретилось). Следующая буква однозначно задаёт новое состояние, и переходы — это автомат Кнута — Морриса — Пратта: при несовпадении откатываемся по префикс-функции, а не в ноль. Последовательность длины n без слова — путь из n переходов из состояния 0, который ни разу не приходит в |w|. Число таких путей — сумма первой строки Tⁿ, где T_st — сколько букв переводят из s в t.

4Разбор

Префикс-функция слова, затем для каждого состояния s и каждой буквы — новое состояние: пока буква не продолжает совпадение, откатываемся k ← fail[k]; если продолжает — k + 1. Переход в |w| в матрицу не пишем. Матрица |w| × |w|, не больше 15 × 15, в степени n — меньше 120 произведений по модулю. Ответ — сумма первой строки.

Проверка на маленьком: n = 3, слово AA. Всего 64 слова, в 7 из них есть AA (AAx, xAA, и AAA посчитано дважды) — остаётся 57. Для EcoRI и длины генома лямбды — второй пример. Случайная последовательность такой длины почти наверняка содержит GAATTC около дюжины раз, а последовательностей совсем без него — доля около 7·10⁻⁶ от всех 4ⁿ.

4+Решение

5Сложность

O(|w|³ log n): 15³ · 120 ≈ 4·10⁵ умножений. Перебор или динамика по позициям текста — O(n·|w|) — для n до 10¹⁸ невозможны, но годятся для проверки на маленьких n.

6Типичные ошибки

Откат в начало. Автомат, который при несовпадении идёт в 0 (или в 1, если буква совпала с первой), неверен для слов, у которых начало повторяется внутри: GGATCC, GAGAGAC, AAC.
Формула включений-исключений «в лоб». 4ⁿ − (n − |w| + 1)·4^n−|w| не учитывает, что слово может встретиться несколько раз и даже внахлёст.
Текст короче слова. Тогда слово не встречается никогда, ответ — 4ⁿ.

Алгоритмы задачи

NUM Алгоритм Матрицы и рекуррентности Степень матрицы: пути длины k в графе, линейные рекуррентности, матрица переноса и цепи Маркова. O(m³ log k) для A^k размера m × m 2 задачи STR Алгоритм Префикс-функция и КМП Все вхождения образца за O(n + m) без шагов назад по тексту; префикс-функция находит и период строки. O(n + m) 2 задачи