teacher
Sign in

Matrix Exponentiation

Turn a linear recurrence or a walk-counting question into one matrix, then raise it to a huge power in O(d^3 log n) with repeated squaring.

40 minCF 1500–23005 interactive12 problems

The problem

Fibonacci numbers are defined by F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2). Print F(n) mod (109+7)F(n) \bmod (10^9 + 7) for nn up to 101810^{18}.

Other questions with the same shape:

  • A recurrence like f(n)=3f(n−1)+2f(n−2)+5f(n) = 3f(n-1) + 2f(n-2) + 5 with a huge nn.
  • A directed graph with 50 vertices: in how many ways can you walk exactly k=1018k = 10^{18} edges from vertex 1 to vertex 50?
1 of 9