BIGOF04-editorial

Problem Link :

Contest
Practice

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