Problem Link :
Author: Amrutansu Garanaik , Abhishek Patnaik
Tester: Keshow Sablaka, Amit Das
Editorialist: Amrutansu Garanaik , Amit Kumar Sahu
Difficulty :
easy-medium
Pre-requisite
matrix multiplication, graph theory, matrix exponentiation ## Problem : Given a graph and some queries. Each query is of form a b. You are also given a length L. You have to find the number of distinct path of length L between the nodes a and b.Explanation
The problem is based on a graph theory theorem. When you have the adjacency matrix of a graph, if we raise the matrix to the power of L, each cell (i,j) will give the number of paths of length L between nodes i and j. The proof is given in any graph theory book and discrete mathematics book.
So the problem reduces to finding the adjacency matrix raised to the power L. The matrix multiplication can be done in O(n^3) times, where n is the number of nodes in the graph. The exponentiation can be done in O(log L) time using modular exponentiation. So overall complexity is O(n^3 log L).
Setter Solution