06/04/2025 15:44:47

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

583. Браки по расчету

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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

Пример вывода

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)