### DemonStar's blog

By DemonStar, history, 3 months ago, ,

Graph Paths — I

I am trying to solve this problem using matrix exponentiation but it is giving Wrong Answer.

My Code

Can someone figure out what I am doing wrong.

• +3

 » 3 months ago, # |   0 Auto comment: topic has been updated by DemonStar (previous revision, new revision, compare).
 » 3 months ago, # |   +6 There can be more than one path from a to b. So, change to: v[a-1][b-1]++;
•  » » 3 months ago, # ^ |   0 Thanks, it worked.
 » 3 months ago, # |   0 Can you explain me how are you using matrix exponentiation here?
•  » » 3 months ago, # ^ |   0 If 'M' is the adjacency matrix of an unweighted graph, then the matrix M raised to the power K gives the number of paths from a to b with exactly K edges for each node pair (a, b)
•  » » » 2 months ago, # ^ |   0 DemonStar I find it difficult to understand this explanation. I mean Why does it work?
 » 3 months ago, # |   0 Similar Problem: https://www.codechef.com/PCR12020/problems/STIMEMCH
 » 6 weeks ago, # |   0 Can you explain how do you use matrix expo here
 » 6 weeks ago, # |   0 This explains it in more detail https://cp-algorithms.com/graph/fixed_length_paths.html