Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

DemonStar's blog

By DemonStar, history, 7 weeks ago, In English,

Graph Paths — I

Link to the Problem Statement

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.

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by DemonStar (previous revision, new revision, compare).

»
7 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

There can be more than one path from a to b. So, change to: v[a-1][b-1]++;

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you explain me how are you using matrix exponentiation here?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      DemonStar I find it difficult to understand this explanation. I mean Why does it work?

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you explain how do you use matrix expo here

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it