vamaddur's blog

Number of Paths Between A and B of Length N in a Directed Graph
By vamaddur, history, 7 years ago, In English

More Detailed Problem Description

I understand the theory for this problem (fast matrix exponentiation), but I need a problem to test my code on, as I was not able to find one after multiple Internet searches. Could someone please provide a problem that asks for a solution along these lines?

Thanks in advance!

  • Vote: I like it
  • -16
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

166E - Tetrahedron: This is basically same problem, but here you are given the graph in problem statement.

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

http://mirror.codeforces.com/gym/101081/problem/G

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

    Hey lucaasdamaso, Could you take a look at my code? I've tried to solve it, but It gave me "wrong answer on test 15" https://ideone.com/FvMNbo

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      its possible a situation where the number of paths is 0 modulo 1e9+7, so u have to print 0 instead of -1. sorry for bad english

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

        That was my mistake. Thanks lucaasdamaso!

        → Reply