Подсчет числа комбинаторных объектов

Во всех задачах этого листка необходимо подсчитать количество комбинаторных объектов, удовлетворяющих данным ограничениям. Рекурсия не поможет — используйте динамическое программирование.

A: Последовательности из 0 и 1 без двух единиц подряд

По данному натуральному n определите количество последовательностей длины n из 0 и 1, не содержащих двух единиц подряд. Гарантируется, что ответ не превосходит 231-1.

Пример

Ввод Вывод 
5
 
13

B: Последовательности из 0, 1, 2 без двух единиц подряд

По данному натуральному n определите количество последовательностей длины n из 0, 1 и 2, не содержащих двух единиц подряд. Гарантируется, что ответ не превосходит 231-1.

Пример

Ввод Вывод 
2
 
8

C: Последовательности из 0, 1, 2 без двух единиц и двоек подряд

По данному натуральному n определите количество последовательностей длины n из 0, 1 и 2, не содержащих двух единиц подряд и двух двоек подряд. Гарантируется, что ответ не превосходит 231-1.

Пример

Ввод Вывод 
2
 
7

D: Последовательности из 0 и 1 без трех единиц подряд

По данному натуральному n определите количество последовательностей длины n из 0 и 1, не содержащих трех единиц подряд. Гарантируется, что ответ не превосходит 231-1.

Пример

Ввод Вывод 
3
 
7

E: Последовательности из 0 и 1 без трех одинаковых символов подряд

По данному натуральному n определите количество последовательностей длины n из 0 и 1, не содержащих трех одинаковых символов подряд. Гарантируется, что ответ не превосходит 231-1.

Пример

Ввод Вывод 
3
 
6

F: Последовательности из 0 и 1 без k единиц подряд

По данным натуральным n и k определите количество последовательностей длины n из 0 и 1, не содержащих k единиц подряд. n≤106, 1≤k≤n+1. Гарантируется, что ответ не превосходит 231-1.

Пример

Ввод Вывод 
3 3


7






5 2


13







G: Последовательности из 0 и 1 без k одинаковых символов подряд



По данным натуральным n и  k определите количество последовательностей длины
n из 0 и 1, не содержащих k одинаковых символов подряд.
n≤106, 2≤k≤n+1.
Гарантируется, что ответ не превосходит 231-1.


Пример







Ввод
Вывод





3 3


6






100 2


2







H: Плавные числа



Назовем число плавным, если его две соседние цифры различаются не более,
чем на 1. По данному натуральному n определите количество плавных натуральных чисел,
имеющих длину  n.
Гарантируется, что ответ не превосходит 231-1.


Пример







Ввод
Вывод





1


9






2


26








I: Ход коня



Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы
набирались на кнопочном телефоне ходом коня. Например, ходом
коня набирается телефон 340-49-27. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.


Вид клавиатуры телефона:




123


456


789


 0 






Напишите программу, определяющую количество телефонных номеров длины N,
набираемых ходом коня. Программа получает на вход натуральное число N
и должна вывести искомое количество телефонных номеров.
Гарантируется, что ответ не превосходит 231-1.


Пример







Ввод
Вывод





2


16








J: Бросание кубика



Кубик, грани которого помечены цифрами от 1 до 6,
бросают N раз. Определите вероятность того, что сумма выпавших
чисел будет в точности равна Q.


Программа получает на вход два целых числа: N и Q
(1≤N≤500, 1≤Q≤3000).
Программа должна вывести единственное действительное число:
искомую вероятность с точностью не менее чем 10-6.
				

Пример







Ввод
Вывод





1 6


0.166667






1 7


0






4 14


0.112654






100 100


1.53065e-78








Указание. Искомая вероятность равна отношению числа
последовательностей длины N, составленных из чисел от 1 до 6,
дающих в сумме число Q, к числу всех таких
последовательностей длины N.


K: Пилообразные последовательности



Назовем последовательность пилообразной, если каждый ее элемент
либо строго больше, либо строго меньше своих соседей. По данными числам
n и k определите число пилообразных
последовательностей длины n, составленных из чисел 1..k.


Программа получает на вход два натуральных числа n и k,
не превосходящих 106. 
Гарантируется, что ответ не превосходит 231-1.


Пример







Ввод
Вывод





3 3


10








L: Пилообразные последовательности (*)



Решите предыдущую задачу в ограничениях: 1≤n≤1000,
1≤k≤1000, ограничение по памяти — 3 Мбайт,
необходимо вывести остаток от деления количества искомых последовательностей
на 109+7.


Пример







Ввод
Вывод





1000 1000


708820568









M: Количество разбиений на слагаемые



Для данных натуральных чисел n и k  определите
количество способов представить число n в виде суммы натуральных слагаемых,
не превосходящих k,
если способы, отличающиеся только порядком слагаемых считать одинаковыми.


Программа получает на вход два натуральных числа n и k,
не превосходящих 120.
Гарантируется, что ответ не превосходит 231-1.


Пример







Ввод
Вывод





5 3


5








N: Количество разбиений на k слагаемых


Для данных натуральных чисел n и k  определите
количество способов представить число n в виде суммы k
натуральных слагаемых,
если способы, отличающиеся только порядком слагаемых считать одинаковыми.


Программа получает на вход два натуральных числа n и k,
не превосходящих 150. Гарантируется, что ответ не превосходит 231-1.


Эту задачу разрешается (и рекомендуется) решать, при помощи Memoization.


Пример







Ввод
Вывод





6 3


3









O: Количество правильных скобочных последовательностей


По данному натуральному n определите количество
правильных скобочных последовательностей, составленных
из n открывающихся и n закрывающихся круглых скобок.


Программа получает на вход натуральное число n, не превосходящее
1000. Неоходимо вывести остаток от деления числа искомых последовательностей
на 109+7.


Пример







Ввод
Вывод





3


5








P: Количество ПСП, где внутри квадратных скобок нет круглых


По данному натуральному n определите количество
правильных скобочных последовательностей длины 2n, составленных
из круглых и квадратных скобок так,что внутри любой пары круглых скобок нет
квадратных скобок..


Программа получает на вход натуральное число n, не превосходящее
1000. Неоходимо вывести остаток от деления числа искомых последовательностей
на 109+7.


Пример







Ввод
Вывод





1


2






2


7









Q: Количество ПСП, вложенности k



По данным числам n и k
определите количество правильных скобочных последовательностей
длины 2n, составленных из круглых скобок, максимальная
вложенность скобок в которой составляет в точности  k.


Программа получает на вход два натуральных числа n и k
(1≤k≤n≤50). Необходимо вывести
остаток от деления числа искомых последовательностей на 109+7.


Пример







Ввод
Вывод





3 1


1






3 2


3






3 3


1








R: Монобиллиард


Маг Стигиус, глава великого войска Коалиции, всё
собрание просидел молча, затем незаметно встал и удалился
в свой кабинет. Конечно, его волновали обсуждавшиеся
там вопросы, и он даже имел некоторые соображения
относительно состава новой армии, но куда больше ему
хотелось побыть наедине и подумать о предстоящей битве.


Все самые гениальные планы сражений Стигиус
придумывал в своём кабинете во время игры в монобильярд,
смысл которой — на специально оборудованном столе
закатывать шары в единственную лузу. У мага было всего
два шара, чёрный и белый, и на протяжении всей игры он
либо закатывал шар одного из цветов в лузу, либо доставал
из лузы тот шар, который был забит в неё последним.


Стигиус все свои действия записывал в специальный
протокол игры, в котором делал 4 типа пометок:
W+, B+, если он закатывал в лузу белый или чёрный
шар соответственно, либо W-, B-, если он извлекал
из лузы шар соответствующего цвета. Корректной
последовательностью выше перечисленных пометок
называется последовательность, которая может являться
протоколом некоторой игры Стигиуса. Например,
W+B+B-W- — корректная последовательность, а W+B+W-B- — нет.
Стигиуса всё время волновал вопрос: сколько существует
различных корректных последовательностей, состоящих
ровно из N пометок? Сможете ли Вы помочь Стигиусу
ответить на него?


Программа получает на вход натуральное число N, не превосходящее 50000.
Программа должна вывести остаток от деления на 109+7  количества различных
корректных последовательностей из N пометок.


Пример







Ввод
Вывод





1


2






2


4









S: Марсианские тарелки



В марсианском ресторане могут готовить N блюд,
а воскресный обед состоит из L блюд.
Некоторые из них могут появиться на воскресном обеде более одного раза,
некоторые могут вообще не появиться. Во время обеда тарелки складываются одна
на другую. Офицант ровно 2L раз заходит в зал и либо
приносит очередное блюдо (после того, как съедено блюдо с верхней
тарелки), либо забирает пустую верхнюю тарелку.
Тем не менее для некоторых упорядоченных пар блюд существует
марсианский обычай: первые из блюд не могут появиться в зале
пока на столе стоят тарелки от вторых.
Такие пары называются несовместимыми.



Назовем расписанием для офицанта порядок, в котором он
приносит и уносит тарелки. Таким образом, мы имеем
2L=T событий в расписании.
Вы должны вычислить количество различных расписаний
для воскресного обеда из L блюд по модулю 109+7.


Программа получает на вход чётное число
T — количество событий в расписании
(1≤T≤200), N —
количество блюд в ресторане (1≤N≤10)
и M — количество несовместимых пар
(1≤M≤100).
Каждая из следующих M строк содержит пару чисел
i и j, которые означают,
что тарелка j не может быть принесена пока на столе стоит
тарелка с номером i.


Программа должна вывести одно число —
остаток от деления количества различных расписаний
на 109+7.


В этой задаче ограничение по времени работы программы — 2 секунды.


Пример







Ввод
Вывод





4 2 1
1 2


7






6 10 2
2 3
6 7


4866









Примечание к первому примеру. Если обозначить принос
тарелки с блюдом 1 как “+1”, а унос тарелки с блюдом 1, как
“−1” и т.д., то возможны такие расписания:

+1 +1 −1 −1
+1 −1 +1 −1
+2 +2 −2 −2
+2 −2 +2 −2
+1 −1 +2 −2
+2 −2 +1 −1
+2 +1 −1 −2