~/problems
Problems
Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.
Matrix exponentiation
Linear recurrences in O(k^3 log n).
Notes
Recognise it when: you need the n-th term of a linear recurrence with huge n (Fibonacci mod p), or the number of paths of length k in a graph.
Write the recurrence as v_{n+1} = M v_n and compute M^n by repeated squaring. That's O(k^3 log n) for a k×k matrix.
Fibonacci: M = [[1, 1], [1, 0]].
4 problems
Advanced & competitive
Number theory Modular arithmetic, primes, matrix powers.
Matrix exponentiation
- Basics: matrix multiply and matrix power basics easy
- Seed library with donations py · c++ · java easy
- N-th Tribonacci Number easy
- Huge Fibonacci numbers mod p py · c++ · java easy