Задание EGEINF0F204A: Подсчёт путей в графе

Путь определяется последовательностью дорог, а движение разрешено только по стрелкам. Для каждой вершины будем складывать количества путей, приходящих по разным последним дорогам: такие наборы не пересекаются.
Все города можно обработать в порядке А, Б, В, Г, Д, З, Е, Ж, И, Л, К, М: каждая дорога ведёт от более раннего города в этом списке к более позднему. Это также показывает, что вернуться в прежний город невозможно.
Пусть N(X) — число путей из А в X. Задаём N(А) = 1: единственный пустой начальный путь служит основой для продолжений. Для остальных городов складываем значения всех непосредственных предшественников.
N(Б) = N(А) = 1.
N(В) = N(А) + N(Б) = 1 + 1 = 2.
N(Г) = N(Б) + N(В) = 1 + 2 = 3.
N(Д) = N(Г) = 3.
N(З) = N(Г) = 3.
N(Е) = N(Г) + N(Д) = 3 + 3 = 6.
N(Ж) = N(Г) + N(Е) + N(З) = 3 + 6 + 3 = 12.
N(И) = N(Д) + N(Е) = 3 + 6 = 9.
N(Л) = N(Ж) + N(З) = 12 + 3 = 15.
N(К) = N(Е) + N(Ж) + N(И) + N(Л) = 6 + 12 + 9 + 15 = 42.
N(М) = N(И) + N(К) + N(Л) = 9 + 42 + 15 = 66.
Независимо посчитаем продолжения с конца. Пусть Q(X) — число путей из X в М. Начинаем с Q(М) = 1; затем для каждого города складываем Q его непосредственных следующих городов.
Q(К) = Q(М) = 1.
Q(Л) = Q(К) + Q(М) = 1 + 1 = 2.
Q(И) = Q(К) + Q(М) = 1 + 1 = 2.
Q(Ж) = Q(К) + Q(Л) = 1 + 2 = 3.
Q(Е) = Q(Ж) + Q(И) + Q(К) = 3 + 2 + 1 = 6.
Q(З) = Q(Ж) + Q(Л) = 3 + 2 = 5.
Q(Д) = Q(Е) + Q(И) = 6 + 2 = 8.
Q(Г) = Q(Д) + Q(Е) + Q(Ж) + Q(З) = 8 + 6 + 3 + 5 = 22.
Q(В) = Q(Г) = 22.
Q(Б) = Q(В) + Q(Г) = 22 + 22 = 44.
Q(А) = Q(Б) + Q(В) = 44 + 22 = 66.
Каждый нужный маршрут единственным образом состоит из пути до К и пути после К. Любую первую часть можно соединить с любой второй: общая промежуточная вершина означала бы цикл, которого в схеме нет.
По правилу произведения получаем N(К) · Q(К) = 42 · 1 = 42.
Проверка: общий подсчёт вперёд N(М) = 66 совпадает с обратным Q(А) = 66. При этом для ответа взято произведение только частей через обязательный город К.
Ответ: 42.