Math -> Linear Recurrence And Matrix Exponentiation

Fixed-width linear recurrences and repeated small linear transitions, turned into companion matrices and powered quickly by repeated squaring.

• Topic slug: math/linear-recurrence
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 1
• Repo companion pages: 3
• Curated external problems: 3

Microtopics

• companion-matrix
• state-vector
• matrix-power
• linear-transition
• recurrence-jump
• fast-doubling-compare

Learning Sources

Source	Type
cp-algorithms Fibonacci numbers	Reference
Competitive Programmer's Handbook	Reference
Principles of Algorithmic Problem Solving	Reference

Practice Sources

Source	Type
CSES Throwing Dice	Practice
CSES Fibonacci Numbers	Practice
CSES Graph Paths I	Practice

Repo Companion Material

Material	Type
Linear Recurrence hot sheet	quick reference
Throwing Dice	flagship note
Template Library exact starter route	starter route

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Fibonacci Numbers	CSES	Medium	Matrix/Recurrence	Math; Implementation	Binary Exponentiation; Modular Arithmetic	Matrix Exponentiation; Fibonacci; Fast Doubling Compare	The smallest exact recurrence-lifting example and the cleanest compare point against fast doubling.
Throwing Dice	CSES	Medium	DP/Recurrences	Dynamic Programming; Math	Basic DP; Modular Arithmetic	Matrix Exponentiation; Companion Matrix; Mod Arithmetic	A fixed-width order-6 recurrence where huge n turns an ordinary DP into a companion-matrix route.

Stretch

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Graph Paths I	CSES	Hard	Graphs/Walk Counting	Graphs; Math	Matrix Exponentiation; Graph Modeling	Matrix Exponentiation; Adjacency Matrix; Walk Counting	Shows the same repeated-linear-transition worldview outside one-dimensional recurrences.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
THROWINGDICE	Throwing Dice	primary	medium	linear recurrence; companion matrix; matrix exponentiation	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py