Задача на 25 баллов на Puthon решение НТО.

Question

Помогите решить задачу на Puthon всем кто решит зарание огромное спасибо
Проектируем мост (25 баллов) 
Ограничение времени	1 секунда 
Ограничение памяти	64Mb 
Ввод	стандартный ввод или input.txt 
Вывод	стандартный вывод или output.txt 
При постройке моста используются два типа пролетов: П-образные (они прочные, но дорогие) и Т-образные (они дешевле, но менее надежные). Мост должен начинаться и заканчиваться П-образными пролетами. Любой Т-образный пролет должен иметь хотя бы один П-образный пролет в качестве соседнего. 
 
Длина проектируемого моста — n пролетов. Муниципалитет выделил средства на постройку a П-образных и b Т-образных пролетов. При этом a + b = n. Требуется выяснить сколькими способами при этих условиях можно скомпоновать мост. Два способа компоновки моста отличаются, если в одной на некоторой позиции стоит П-образный пролет, а в другой на этой же позиции стоит Т-образный пролет. 
 
Формат ввода 
В одной строке через пробел заданы два числа a — число П-образных пролетов и b — число Т-образных пролетов, на постройку которых выделены средства. 2 ≤ a ≤ 106, 0 ≤ b ≤ 106. 
 
Формат вывода 
Вывести одно число — количество вариантов компоновки моста. Так как ответ может быть очень большим, требуется вывести остаток от его деления на 1000000007 (109 + 7). 
 
Пример 
Ввод	Вывод 
4 3 
7 
Примечания 
Для примера из условия имеется 7 вариантов компоновки моста (пробелы добавлены для лучшего восприятия вариантов): 
 
П Т Т П Т П П 
 
П Т Т П П Т П 
 
П Т П Т Т П П 
 
П Т П П Т Т П 
 
П П Т П Т Т П 
 
П П Т Т П Т П 
 
П Т П Т П Т П

luxury brain · Answer

привет! давай разберемся с задачей. нам необходимо построить мост с использованием п-образных и т-образных пролетов, соблюдая определенные правила. основные правила, которые нужно учитывать:1. мост должен начинаться и заканчиваться п-образными пролетами.2. т-образные пролеты должны иметь хотя бы одного п-образного соседа. это значит, что они не могут быть соседями друг с другом.теперь можно перейти к решению. мы можем использовать динамическое программирование для подсчета количества способов собрать мост. нам нужно будет хранить состояния, которые будут учитывать, какие пролеты находятся в конце.вот пример реализации на python:```pythondef count_bridge_ways(a, b):    mod = 1000000007    # если t-образных пролетов нет    if b == 0:        return 1    # dp[i] обозначает количество способов построить мост с i p и j t    # инициализируем массив dp    dp = [0] * (b + 1)    dp[0] = 1  # один способ построить мост без t-пролетов: просто p    # подсчет вариантов для каждого количества т-образных пролетов    for i in range(1, a + 1):  # перебираем количество п-пролетов        new_dp = [0] * (b + 1)        for j in range(min(i, b) + 1):  # перебираем количество т-пролетов            if j == 0:                new_dp[j] = dp[j]            else:                new_dp[j] = (dp[j] + new_dp[j - 1]) % mod                        # обновляем с учетом добавления одного п в конце            if j - 1 >= 0:                new_dp[j] = (new_dp[j] + dp[j - 1]) % mod        dp = new_dp        return dp[b]# читаем входные данныеa, b = map(int, input().split())result = count_bridge_ways(a, b)print(result)```в этой программе мы создаем массив `dp`, чтобы хранить количество возможных компоновок. мы проходим через количество п-пролетов и обновляем массив, учитывая условия задачи. в конце выводим количество способов.надеюсь, это поможет тебе с задачей! если есть вопросы, задавай!