Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
583. Браки по расчету
Модулярная арифметикаГенерация всех подмножеств, сочетаний, перестановок
Динамическое программирование и запоминающие функции
Олимпиадные задачи на русском языке
| 12/10/2007 | Личное первенство Южного Урала (A) |
| 17/10/2007 | Занятие 6 (дорешивание) (A) |
| 10/07/2023 | Лето 2023-7 сложные (D) |
| 07/03/2024 | ДП (повторение) (проводит BOGAT) (A) |
| 03/04/2024 | ДП по подмножествам, по профилю (проводит BOGAT) (A) |
| 08/07/2024 | Лето 2024-7 сложные (D) |
| 31/10/2025 | ЦОП2: ДП по подмножествам (проводит BOGAT) (A) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Королевство Флатландия оказалось на грани войны, так как южные князья поссорились с северными. С каждой стороны в ссоре участвовало по `N` княжеств. Чтобы укрепить отношения между княжествами, король повелел заключить `N` браков между принцами и принцессами противников, чтобы из каждого княжества, участвовавшего в ссоре, кто-то вышел замуж или женился.
Герольдмейстер вычислил для каждой пары княжеств количество возможных способов заключить брак между их принцами и принцессами (c учетом пола, возраста и пожеланий сторон), и теперь хочет знать общее количество вариантов заключения `N` браков, удовлетворяющих требованиям короля. Так как число вариантов может быть очень велико, достаточно вычислить остаток от деления результата на число `P`.
Первая строка ввода содержит два целых числа `N` (`1\ ≤\ N\ ≤\ 20`) и `P` (`2\ ≤\ P\ ≤\ 10000`). Далее следует `N` строк, в каждой строке `N` целых чисел в диапазоне от 0 до 100. Число в `i`-й строке `j`-м столбце означает количество возможных способов заключить брак между `i`-м южным княжеством и `j`-м северным княжеством.
Вывести одно целое число – остаток от деления на `P` общего количества вариантов заключения `N` браков.
Пример ввода
2 100 2 3 1 4
Пример вывода
11
