Подразделы

Другие разделы

Дата и время

09/04/2025 00:49:57

Авторизация

Задачи очного тура личного первенства

A. Браки по расчету B. Broken Sword: потерянный файл C. Кредитный калькулятор D. Draw Grid E. Морской бой F. Фантастическая 4 G. Go Scoring H. Среднее арифметическое I. Лабиринт

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

Ограничения: время – 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

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