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

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