Сервер олимпиад

Ставропольский государственный университет

Имя
Пароль

Server Off-Line
Server time: 04 Mar 2021 02:41:27

Банк задач


Номер задачи - 8

Задача Диагонали

Ограничение: 2 секунды на тест.

Диагональю квадратной матрицы размера N×N назовем множество из N ячеек этой матрицы, таких что никакие две ячейки этого множества не находятся в одной и той же строке или столбце. Нетрудно убедиться, что матрица имеет ровно N! диагоналей.

0 1 0 1 1
1 0 1 1 1
2 1 3 1 2
2 1 2 2 2
2 1 1 1 1
a b c
d e f
g h i
1. {a, e, i}
2. {a, f, h}
3. {b, d, i}
4. {b, i, d}
5. {c, d, h}
6. {c, h, d}
Рис 1. Матрица и одна из ее диагоналей. Рис 2. Все диагонали матрицы 3×3.

Величиной диагонали назовем произведение всех элементов, лежащих на данной диагонали.

Напишите программу, которая вычислит сумму величин всех N! диагоналей данной матрицы N×N.

Формат входных данных

Первая строка входного файла содержит целое число N — размер матрицы. 1 ≤ N ≤ 15. Матрица задается в следующих N строках, каждая из которых содержит N целых чисел через пробел. Числа по модулю не превышают 109. Также вы можете быть уверены, что во всех тестах сумма величин всех диагоналей не превышает по модулю 1018. (Однако значения отдельных диагоналей могут быть значительно больше).

Формат выходных данных

Одно число — точное значение суммы всех диагоналей матрицы, заданной на входе.

Примеры
ВходВыход
2
1 2
3 4
10
5
0 1 0 1 1
1 0 1 1 1
2 1 3 1 2
2 1 2 2 2
2 1 1 1 1
239
2
999999999 999999999
999999999 -999999999
0
Rambler's Top100 | Карта сайта | Контакты | Copyright © 2005-2007, Ставропольский государственный университет.