Задачи / Статистика /

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

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

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

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

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

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

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

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