Задача №112638. Вернуться за K перелётов
Вася решил немного попутешествовать и выяснил, что между некоторыми городами нет прямых авиарейсов, поэтому придётся лететь с пересадками. Ему стало интересно, можно ли запланировать замкнутый маршрут (который начинается и заканчивается в одном и том же городе), в котором ровно K перелётов. Напишите программу, которая выводит количество таких различных циклических маршрутов. Маршруты, которые проходят через одни и те же города в том же порядке и сводятся только к сдвигу начальной точки цикла (например, 1-2-3-1 и 2-3-1-2), считаются одинаковыми.
В первой строке вводится количество городов на карте N ( 1 ≤ N ≤ 50 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы матрицы смежности графа, который описывает схему авиационных сообщений. В последней строке вводится число перелётов K .
Программа должна вывести одно число: количество всех различных замкнутых маршрутов, состоящих из K перелётов.
5 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 3
2