### 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. cses, math, Comments (9)
 » Auto comment: topic has been updated by DemonStar (previous revision, new revision, compare).
 » There can be more than one path from a to b. So, change to: v[a-1][b-1]++;
•  » » Thanks, it worked.
 » Can you explain me how are you using matrix exponentiation here?
•  » » 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)
•  » » » DemonStar I find it difficult to understand this explanation. I mean Why does it work?
 » Similar Problem: https://www.codechef.com/PCR12020/problems/STIMEMCH
 » Can you explain how do you use matrix expo here
 » This explains it in more detail https://cp-algorithms.com/graph/fixed_length_paths.html