Форум программистов, компьютерный форум CyberForum.ru

Задача на ДП - C++

Восстановить пароль Регистрация
 
Prim
0 / 0 / 0
Регистрация: 25.04.2013
Сообщений: 3
25.04.2013, 17:47     Задача на ДП #1
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт


У Пети есть полоска бумаги, разделенная на N клеток. Он хочет раскрасить каждую клетку в
синий, красный или зеленый цвет.
Кроме этого, Пете интересны одноцветные отрезки. Петя называет одноцветным отрезком
несколько подряд идущих клеток, раскрашенных в один цвет и ограниченных с обеих сторон клет-
ками другого цвета или границами полоски.
Петя хочет, чтобы все синие одноцветные отрезки имели длину A клеток, все красные одноцвет-
ные отрезки имели длину B клеток, а все зеленые одноцветные отрезки имели длину C клеток.
Пете интересно, сколькими способами он может раскрасить полоску таким образом. Помогите
ему и вычислите это количество. Поскольку оно может быть очень большим, выведите его по модулю 109+7.
Формат входного файла
В первой строке записано четыре целых числа, разделенных пробелами — N, A, B и C
(1<=A; B; C; N<=106, A; B; C<=N).
Формат выходного файла
Выведите ответ на задачу по модулю 109 + 7.
Примеры
3 1 2 3-3
3 1 1 1-12
5 1 1 1-48
3 2 2 2-0
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 02:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru