Пусть задан ориентированный невзвешенный граф G с n вершинами, и задано целое число k. Требуется для каждой пары вершин i и j найти количество путей между этими вершинами, состоящих ровно из k рёбер. Пути при этом рассматриваются произвольные, не обязательно простые (т.е. вершины могут повторяться сколько угодно раз).

Будем считать, что граф задан матрицей смежности, т.е. матрицей g[][] размера n x n, где каждый элемент g[i][j] равен единице, если между этими вершинами есть ребро, и нулю, если ребра нет. Описываемый ниже алгоритм работает и в случае наличия кратных рёбер: если между какими-то вершинами i и j есть сразу m рёбер, то в матрицу смежности следует записать это число m. Также алгоритм корректно учитывает петли в графе, если таковые имеются.

Очевидно, что в таком виде матрица смежности графа является ответом на задачу при k=1 — она содержит количества путей длины 1 между каждой парой вершин.

Решение будем строить итеративно: пусть ответ для некоторого k найден, покажем, как построить его для k+1. Обозначим через d_k найденную матрицу ответов для k, а через d_{k+1} — матрицу ответов, которую необходимо построить. Тогда очевидна следующая формула:

Легко заметить, что записанная выше формула — не что иное, как произведение двух матриц d_k и g в самом обычном смысле:

Таким образом, решение этой задачи можно представить следующим образом:

Осталось заметить, что возведение матрицы в степень можно произвести эффективно с помощью алгоритма Бинарного возведения в степень.

Итак, полученное решение имеет асимптотику O (n^3 * log k) и заключается в бинарном возведении в k-ую степень матрицы смежности графа. Более подробно и понятно тут

С помощью переливаний, поддерживая для каждой вершины количество вертикальных путей длины $$$l$$$ для всех $$$l$$$ не превосходящих глубину поддерева вершины. Чтобы пересчитать такую величину необходимо при подъеме к предку выбрать у этого предка самого глубокого сына, сдвинуть массив путей на 1 и добавить 1 вертикальный путь длины 1 и указать что такой массив теперь хранит вертикальные пути для вершины-предка, затем прибавлять кол-ва вертикальных путей из других детей. Чтобы при этом пересчитать количество всех путей, необходимо, аккуратно выписывая формулы и поддерживая префиксные суммы, проходить по массивам неглубоких детей. Работает за $$$O(n)$$$ (доказательство сложное, но легко показать что это хотя бы $$$O(n\log{n})$$$, потому что это переливания, и каждый раз, когда ты перекидываешь информацию о вершине, размер множества вершин увеличивается хотя бы вдвое), если правильно работать с векторами для поддержки вертикальных путей.