41 подписчик
Еще одна олимпиадная задачка.
В одной биоинженерной компании по непонятной причине отказали все скрипты.
Так что генетики исследуют последовательности нуклеотидов вручную. Чтобы легче передавать информацию устно, они называют последовательность символов A, G, T, C «читаемой», если рядом ни с одной согласной нет другой согласной, а рядом ни с одной гласной — другой гласной, и предпочитают работать только с такими последовательностями.
Дано число N. Сколько различных читаемых последовательностей длины N существует? Так как ответ может быть очень большим, выведите остаток от его деления на 10**9 + 7.
Самое главное заметить простую закономерность - если последовательность заканчивается на "A", то дальше могут встать
на выбор три буквы. А если на конце не "A", то кол-во последовательностей остается прежним. Далее методом динамического программирования (Получаем результат i-го шага в зависимости от (i-1)-го шага.)
Ссылка на код:
Около минуты
26 июля 2023