Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1325. Мозаика
Модулярная арифметикаДинамическое программирование и запоминающие функции
Олимпиадные задачи на русском языке
| 15/12/2009 | Сборы, группа 1 (3) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Один архитектор захотел украсить свое здание мозаичной полосой из плиток.
У него есть 2 вида кусочков плитки, которые он может использовать для украшения, оба размером 2 на 2 дюйма:
Он может использовать плитки второго вида повернутыми любым из 4-х способов.
Архитектор хочет заполнить все пространство мозаикой из этих плиток без пропусков.
Сейчас он думает над тем, сколько же существует различных вариантов сделать мозаику.
Он считает, что две мозаики одинаковые тогда и только тогда, когда одинакового вида
плитки лежат на одинаковых местах. То есть, если поворот или отражение всей мозаики
не ставит плитки на те же самые места, то эта повернутая или отраженная мозаика будет
считаться различной с исходной.
Например, следующие мозаики получены из первой с помощью поворотов и
отражений, но все они будут считаться различными:
В единственной строке ввода содержатся два целых числа `N`
и `M` (`2\ ≤\ N\ ≤\ 10`, `2\ ≤\ M\ ≤\ 500`) – соответственно высота и ширина полосы,
которую необходимо покрыть мозаикой.
Вывести одно целое число – остаток от деления количества различных способов замощения заданной полосы на `10^6`.
Пример ввода 1
2 10
Пример вывода 1
25
Пример ввода 2
4 16
Пример вывода 2
366318
Пример ввода 3
4 50
Пример вывода 3
574777
