Не могу решить задание
Я участвую в школьной олимпиаде, и совсем не могу решить последнее задание.
Вот условие задачи:
Чтобы легче передавать информацию устно, они называют последовательность символов A, G, T, C «читаемой», если рядом ни с одной согласной нет другой согласной, а рядом ни с одной гласной — другой гласной, и предпочитают работать только с такими последовательностями.
Дано число N. Сколько различных читаемых последовательностей длины N существует? Так как ответ может быть очень большим, выведите остаток от его деления на 10^9 + 7.
Но также есть ограничение на время исполнения(1 секунда)
вот одна из моих попыток написать что-то
import string
import random, re
N=10
words= [random.choice(string.ascii_uppercase) for i in range(N)]
st_r = ""
word=(str_r.join(words))
glasniye = len(re.findall(r'[AEIOUY]', word))
soglasniye = len(re.findall(r'[BCDFGHJKLMNPQRSTVWXYZ]', word))
До этой олимпиады никогда не писал на питоне.
Ответы (1 шт):
Давайте выведем формулу для чётной длины.
Если строка начинается с "A", то она имеет вид A*A*A*A*, где вместо звёздочек стоят любые из символов "G","C","T".
При длине N в строке N//2 мест для этих согласных.
Для каждого места есть три варианта, итого таких строк 3**N//2.
Аналогично для случая, когда строка начинается с согласной *A*A*A*A. Итого 2*3**N//2 вариантов.
Осталось сделать подобные вычисления для нечётной длины - строки вида А*A*A*A и *A*A*A*