Назовём число красивым если любые две его соседние цифры образуют двузначное число, которое делится либо на 17, либо на 23. Для каждого натурального n (n больше или равно 2) найдите количество n-значных красивых чисел.
Для решения этой задачи можно воспользоваться динамическим программированием. Пусть dp[i][j] - количество i-значных чисел, у которых последняя цифра равна j и они являются красивыми.
Используя это определение, мы можем создать следующие рекуррентные соотношения:
dp[i][j] = sum(dp[i-1][k]), где k является таким числом, что числа j10 + k или j10 + j образуют двузначное число, которое делится на 17 или 23.
Таким образом, мы можем выразить количество n-значных красивых чисел как сумму dp[n][j] для всех возможных j от 0 до 9.
Написанный алгоритм будет иметь асимптотическую сложность O(n*10^2).
Пример кода на Python:
n = 3 # задаем значение n MOD = 10**9 + 7 dp = [[0] * 10 for _ in range(n+1)] for j in range(1, 10): if j*10 % 17 == 0 or j*10 % 23 == 0: dp[2][j] = 1 for i in range(3, n+1): for j in range(10): for k in range(10): if (j*10 + k) % 17 == 0 or (j*10 + k) % 23 == 0 or (j*10 + j) % 17 == 0 or (j*10 + j) % 23 == 0: dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD result = sum(dp[n]) % MOD print(result)
Данный код вычислит количество n-значных красивых чисел для заданного значения n и выведет ответ.
Для решения этой задачи можно воспользоваться динамическим программированием. Пусть dp[i][j] - количество i-значных чисел, у которых последняя цифра равна j и они являются красивыми.
Используя это определение, мы можем создать следующие рекуррентные соотношения:
dp[i][j] = sum(dp[i-1][k]), где k является таким числом, что числа j10 + k или j10 + j образуют двузначное число, которое делится на 17 или 23.
Таким образом, мы можем выразить количество n-значных красивых чисел как сумму dp[n][j] для всех возможных j от 0 до 9.
Написанный алгоритм будет иметь асимптотическую сложность O(n*10^2).
Пример кода на Python:
n = 3 # задаем значение nMOD = 10**9 + 7
dp = [[0] * 10 for _ in range(n+1)]
for j in range(1, 10):
if j*10 % 17 == 0 or j*10 % 23 == 0:
dp[2][j] = 1
for i in range(3, n+1):
for j in range(10):
for k in range(10):
if (j*10 + k) % 17 == 0 or (j*10 + k) % 23 == 0 or (j*10 + j) % 17 == 0 or (j*10 + j) % 23 == 0:
dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD
result = sum(dp[n]) % MOD
print(result)
Данный код вычислит количество n-значных красивых чисел для заданного значения n и выведет ответ.