2

Есть олимпиадная задачка, её суть такова: Дано целое число N. 1 <= N <= 10^9. Необходимо определить количество возможных последовательностей длины N, составленных из символов A, G, T, C при условии, что согласные и гласные буквы в этих последовательностях должны чередоваться. Так как ответ может быть очень большим, вывести его остаток от деления на (10^9 + 7). Ограничение по времени - 1 секунда.

Есть переборное решение, которое проходит тесты с N < 11:

import itertools

n = int(input())
s = "AGTC"
count = 0
for i in itertools.product(s, repeat=n):
    word = "".join(i)
    flag = True
    if word[0] == "A":
        for ind in range(0, len(word), 2):
            if not word[ind] == "A":
                flag = False
                break
        for ind in range(1, len(word), 2):
            if not flag: break
            if not word[ind] in "GTC":
                flag = False
                break

    if word[0] in "GTC":
        for ind in range(0, len(word), 2):
            if not flag: break
            if not word[ind] in "GTC":
                flag = False
                break
        for ind in range(1, len(word), 2):
            if not flag: break
            if not word[ind] == "A":
                flag = False
                break
    if flag:
        count += 1
        
print(count)

Проанализировав закономерность в ответах, были определены формулы, которые позволят вычислить ответ за 1 сек. для значений N < 10^4:

n = int(input())
if n % 2 == 0:
    result = 6 * 3 ** (n // 2 - 1)
else:
    result = 4 * 3 ** ((n - 1) // 2)
print(result % (10**9 + 7))

Нужна помощь с нахождением решения, которое не будет превышать лимит времени 1 сек. для N до 10^9.

1 ответ 1

5

Проблема в том, что при возведении в степень получается уж очень большое число. Однако оно нам нужно не само по себе, а остаток от деления по указанному модулю. Поэтому можно использовать быстрое бинарное возведение в степень по модулю, в ходе работы которого длинные числа появляться не будут. На ваше счастье, в Python есть готовая функция - это pow с третьим аргументом.

Формулы ваши, кстати, можно упростить

2*3**(n//2)
4*3**(n//2)

Пример для чётной части, время мгновенное

n = 8888888888
m = pow(3, n//2, 1000000007)
result = (m + m) % 1000000007
print(result)
3
  • Пробовал просто заменять возведение в степень на pow и всё равно на больших числах время превышало секунду. Или нужно использовать pow не просто как (число, степень, на что делим)? Не особо разбираюсь в этой функции, к сожалению :(
    – magistar
    Commented 27 сент. 2022 в 16:59
  • Привел пример, время очень мало
    – MBo
    Commented 27 сент. 2022 в 17:11
  • Разобрался! Спасибо огромное.
    – magistar
    Commented 27 сент. 2022 в 18:48

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.