PreviousNext
Coding/Graphs and trees

Walks of length k

Write codeHard35 minCitadel style

Your task

You are given an n x n adjacency matrix adj of a directed graph (adj[i][j] == 1 means an edge i to j, else 0), a start node src, a destination node dst, and an integer k. Return the number of distinct walks of EXACTLY k edges from src to dst, modulo 1_000_000_007. n is up to 50 and k can be as large as 10^9, so you must use fast matrix exponentiation rather than DP over k.

Examples

count_walks(adj: list[list[int]], src: int, dst: int, k: int) -> int
Example 1
Inputcount_walks([[0, 1, 0], [0, 0, 1], [1, 0, 0]], 0, 0, 3)
Output1