⚙️AlgorithmIntermediate

Matrix Exponentiation

Key Points

•
Matrix exponentiation turns repeated linear transitions into a single fast power of a matrix using exponentiation by squaring.
•
Any linear recurrence f(n) = $\sum_{i = 1}^{k}$ $c_{i}$ f(n-i) can be encoded as a k×k companion matrix so that a state vector advances by one step via matrix multiplication.
•
Raising a k×k matrix A to the n-th power with binary exponentiation runs in O( $k^{3}$ $lo g$ n) time and O( $k^{2}$ ) space using the standard triple-loop multiply.
•
Classic applications include fast Fibonacci, counting graph walks of fixed length, and jumping many steps in linear DP transitions.
•
For competitive programming, use 64-bit integers with a modulus (e.g., 10^9+7) to avoid overflow and keep results bounded.
•
The (i, j) entry of $A^{n}$ counts the number of length-n walks from node i to node j in a directed graph with adjacency matrix A.
•
Be careful with the order of the state vector and coefficient signs when building the companion matrix; off-by-one mistakes are common.
•
You can sometimes speed up multiplication using bitset tricks for boolean matrices or faster algorithms, but O( $k^{3}$ ) is standard for $k \leq 200$ in contests.

Prerequisites

→Matrix multiplication — Understanding how to multiply matrices and why order matters is essential for exponentiation and building companion matrices.
→Binary exponentiation (fast power) — Matrix exponentiation applies the same technique as scalar fast power but with matrices.
→Linear recurrences — Matrix exponentiation encodes these recurrences into a linear state transition, so recognizing this structure is key.
→Modular arithmetic — Competitive programming solutions often use a modulus to avoid overflow and match problem statements.
→Graphs and adjacency matrices — Powers of adjacency matrices count walks, an important application of matrix exponentiation.
→Asymptotic analysis (Big-O) — To evaluate when O(k^{3} log n) is acceptable and compare alternatives.

Detailed Explanation

Tap terms for definitions

01Overview

Matrix exponentiation is a technique that accelerates repeated linear transformations by converting them into a single fast power of a matrix. Imagine a process where a k-dimensional state evolves step-by-step by multiplying with the same k×k matrix A: after n steps, the state becomes A^{n} times the initial state. Instead of multiplying A repeatedly n times, we compute A^{n} using binary (fast) exponentiation, which needs only O(log n) matrix multiplications. Since each naive matrix multiply takes O(k^{3}) time, the whole procedure runs in O(k^{3} \log n), a huge speedup when n is large. This method is especially powerful for linear recurrences like Fibonacci and Tribonacci: we encode the recurrence into a companion matrix so that advancing one index equals one multiplication by that matrix. It also generalizes to graph problems: the n-th power of an adjacency matrix counts walks of length n between vertices. In dynamic programming, if your transition is linear in the state vector, matrix exponentiation lets you "jump" many steps at once. Overall, matrix exponentiation unifies several problems under a single, efficient computational framework.

02Intuition & Analogies

Hook: Suppose you want to know the population of rabbits after a billion months, and each month the new count depends linearly on the last few months (like Fibonacci). Simulating month-by-month would take forever. What if you could press a "skip ahead by 1,000,000,000" button? Concept: A matrix is like a machine that takes a vector (your current situation) and outputs a new vector (the next situation). If the change from one step to the next is always the same rule, then pressing the button once is multiplying by matrix A. Press it twice: A·A = A^{2}. Press it n times: A^{n}. Now, powering a number is fast with repeated squaring—do the same with matrices. Instead of doing n multiplications, you only do about log2(n) big jumps: square, square, multiply when a binary digit of n is 1. Example: For Fibonacci, the rule is F(n) = F(n−1) + F(n−2). Pack the state as [F(n), F(n−1)]^T. The machine that moves you one month forward is [[1,1],[1,0]]: multiply it by [F(n), F(n−1)]^T to get [F(n+1), F(n)]^T. To jump a billion months, compute this 2×2 matrix to the billionth power using fast exponentiation, then multiply once by the initial state. The same idea works for any fixed linear rule, for counting paths in graphs (walks = repeated adjacency action), and for DP transitions that are linear in the state.

03Formal Definition

Let A

\in

R^{k \times k}

(or over a ring, e.g., integers modulo M). Define the state vector s(n)

\in

R^{k}

. If the system evolves linearly by s(n+1) = A\,s(n), then s(n) =

A^{n}

s(0) for n

\geq

0. Binary exponentiation computes

A^{n}

by expressing n in binary as n =

\sum_{i = 0}^{ℓ}

b_{i}

2^{i} with

b_{i}

\in

\{0,1\}. Then

A^{n}

\prod_{i = 0}^{ℓ}

(A^{2^{i}})^{

b_{i}

}, where A^{2^{i+1}} = (A^{2^{i}})^2. Using the standard O(

k^{3}

) matrix multiplication, this yields O(

k^{3}

lo g

n) time. For a k-term linear recurrence f(n) =

\sum_{i = 1}^{k}

c_{i}

f(n-i), define the companion matrix C

\in

R^{k \times k}

C_{1, i} = c_{i}

for 1

\leq

\leq

C_{i + 1, i} = 1

for 1

\leq

i < k

, and zeros elsewhere. With state vector v(n) = [f(n), f(n-1),

\dots

, f(n-k+1)]^{

T

}, we have v(n) = C\,v(n-1), hence v(n) =

C^{n - (k - 1)}

v(k-1) for n

\geq

k-1. Over a modulus M, all operations are taken modulo M, turning the ring into

Z

Z

. In graphs, for adjacency matrix A of a directed multigraph, (

A^{n}

)_{ij} equals the number of length-n walks from i to j.

04When to Use

Large n, small k: If k (matrix dimension) is modest (e.g., ≤ 200) but n is huge (up to 10^{18}), matrix exponentiation shines with O(k^{3} \log n) time.
Linear recurrences: Any fixed-order linear recurrence with constant coefficients can be handled, including Fibonacci, Tribonacci, linear DP transitions, and problems where the next state is a fixed linear combination of a bounded window of previous states.
Graph walk counts: When you need counts of paths/walks of exact length n between nodes (possibly modulo M). Useful for automata, Markov chain step transitions (over reals), and reachability in exactly n steps (over booleans).
Jump pointers for DP: If your DP transition over a vector is linear, exponentiating the transition matrix lets you move T steps at once, enabling logarithmic-time jumps in answering queries.
Multiple queries with varying n but fixed A: Precompute powers A^{1}, A^{2}, A^{4}, ..., A^{2^{\ell}} (binary lifting) to answer each query in O(k^{3} \log n) or faster if you can cache intermediate multiplications. Avoid it when k is very large (e.g., thousands) and matrices are dense; O(k^{3}) becomes prohibitive unless you exploit sparsity or special structure.

⚠️Common Mistakes

Wrong state ordering: Mixing up the order of the state vector [f(n), f(n-1), ...] leads to incorrect companion matrices. Write out v(n) = C v(n-1) explicitly to verify each row.
Off-by-one in exponent: For recurrences, you usually compute v(n) = C^{n-(k-1)} v(k-1). Forgetting the shift (or using n instead of n−(k−1)) gives answers for the wrong index.
Overflow: Multiplying 64-bit integers without modulus or with too-large modulus (≈ 10^{18}) can overflow. Use a safe modulus (like 10^{9}+7) or implement 128-bit intermediate casts (built-in __int128 in C++).
Forgetting identity matrix: In fast exponentiation, the running result must start as the identity I. Starting with zeros or A yields wrong powers for certain n (especially when n=0 or n has leading zeros).
Misinterpreting adjacency powers: A^{n}_{ij} counts walks (with repeated vertices/edges), not necessarily simple paths. For boolean reachability, use logical OR/AND semiring or treat nonzero as true after the fact.
Non-commutativity: Matrix multiplication is not commutative; the order of multiplication during exponentiation and when applying to vectors matters (A^{n} s(0) is not s(0) A^{n}).
Ignoring sparsity: Dense O(k^{3}) multiply on a very sparse matrix wastes time; using sparse multiplication can reduce complexity significantly.

Key Formulas

Linear evolution

s (n) = A^{n} s (0)

Explanation: If each step applies the same linear transformation A, then after n steps the state equals A raised to the n-th power applied to the initial state. This is the foundation of matrix exponentiation.

Binary expansion of n

n = i = 0 \sum ℓ b_{i} 2^{i}, b_{i} \in {0, 1}

Explanation: We express the exponent n in binary to decide which squared powers A^{2^{i}} to include in the product. This enables exponentiation by squaring.

Product over binary bits

A^{n} = i = 0 \prod ℓ (A^{2^{i}})^{b_{i}}

Explanation: Only the terms with $b_{i} = 1$ contribute to the product; we precompute successive squares A, $A^{2}$ , $A^{4}$ , ... and multiply selected ones. This yields O( $lo g$ n) matrix multiplications.

State advancement via companion matrix

v (n) = C v (n - 1), v (n) = C^{n - (k - 1)} v (k - 1)

Explanation: For a k-term linear recurrence, the state vector stacked with recent values advances one step by multiplying with C. To jump to index n, raise C to the appropriate power and multiply once.

Companion matrix form

C = c_{1} 10 ⋮ 0 c_{2} 01 ⋮ 0 \dots \dots \dots ⋱ \dots c_{k} 00 ⋮ 1

Explanation: This k×k matrix encodes f(n)= $\sum_{i = 1}^{k}$ $c_{i}$ f(n-i) with the first row holding the coefficients and the subdiagonal of ones shifting previous terms. Multiplying C by [f(n-1),...,f(n-k)]^{T} produces f(n).

Walk-count expansion

(A^{n})_{ij} = p_{1}, \dots, p_{n - 1} \sum A_{i p_{1}} A_{p_{1} p_{2}} \dots A_{p_{n - 1} j}

Explanation: The (i,j) entry of $A^{n}$ sums products over all intermediate vertices, counting walks of length n from i to j. This connects matrix powers to path counting in graphs.

Time complexity

T (k, n) = O (k^{3} lo g n)

Explanation: Using the naive O( $k^{3}$ ) multiply and O( $lo g$ n) multiplies from binary exponentiation, the total time is cubic in k and logarithmic in n. This is typically fast for small k and huge n.

Matrix multiply cost

Mult (k) = O (k^{3}), Space (k) = O (k^{2})

Explanation: Standard triple-loop multiplication runs in cubic time and quadratic space to store matrices. Space is dominated by storing a few k×k matrices during exponentiation.

Fibonacci matrix form

[F (n + 1) F (n)] = [1110]^{n} [F (1) F (0)]

Explanation: Fibonacci numbers arise from repeatedly applying the 2×2 transition. Raising the matrix to n and multiplying by the initial vector yields F(n+1) and F(n).

Complexity Analysis

Let k be the matrix dimension and n the exponent. The standard matrix multiplication (three nested loops) costs O(

k^{3}

) arithmetic operations and uses O(

k^{2}

) space to store the matrices. Binary exponentiation represents n in binary and performs O(log n) matrix multiplications: roughly one multiplication per set bit and one squaring per bit position. Thus the total time is O(

k^{3}

lo g

n), and the extra space beyond the input matrices remains O(

k^{2}

), since we store only a constant number of matrices at once (current power, accumulator, and a temporary for multiplication). If the matrix is sparse with m nonzero entries, sparse multiplication can reduce per-multiply cost to roughly O(mk) or O(m

k

) with appropriate data structures; the total then becomes O(

cost_mul

\cdot

lo g

n). For boolean reachability, bitset-optimized multiplication can achieve about O(

k^{3}

/w) where w is the machine word size. Theoretical fast multiplication (Strassen and beyond) reduces O(

k^{3}

) to about O(

k^{2.807}

) or better, which in turn decreases the overall exponentiation time to O(

k^{ω}

lo g

n), but constant factors and implementation complexity usually outweigh benefits for

k \leq a

few hundred in contests. When computing linear recurrences, the effective k is the recurrence order, so time is O(

k^{3}

lo g

n) but often improved in practice because the companion matrix has a very regular, almost-sparse structure. For 2×2 (e.g., Fibonacci), each multiply is O(1), giving O(

lo g

n) time. Always consider modular arithmetic to avoid overflow; using 64-bit with modulus around 10^{9}+7 keeps operations safe and constant-time.

Code Examples

Reusable k×k matrix power (modulo) with binary exponentiation

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Matrix {
5     int n;                      // dimension n x n
6     long long MOD;              // modulus for arithmetic
7     vector<vector<long long>> a;// matrix data
8 
9     Matrix(int n_, long long MOD_, bool ident=false) : n(n_), MOD(MOD_) {
10         a.assign(n, vector<long long>(n, 0));
11         if (ident) {
12             for (int i = 0; i < n; ++i) a[i][i] = 1 % MOD;
13         }
14     }
15 
16     static Matrix identity(int n, long long MOD) { return Matrix(n, MOD, true); }
17 
18     // Matrix multiplication: C = A * B (mod MOD)
19     Matrix operator*(const Matrix &o) const {
20         Matrix r(n, MOD);
21         // Simple triple-loop; can be optimized by loop reordering or blocking
22         for (int i = 0; i < n; ++i) {
23             for (int k = 0; k < n; ++k) {
24                 long long aik = a[i][k];
25                 if (aik == 0) continue; // small optimization for sparse rows
26                 for (int j = 0; j < n; ++j) {
27                     r.a[i][j] = (r.a[i][j] + aik * o.a[k][j]) % MOD;
28                 }
29             }
30         }
31         return r;
32     }
33 
34     // Fast exponentiation: returns A^p (mod MOD)
35     Matrix pow(long long p) const {
36         Matrix base = *this;
37         Matrix res = Matrix::identity(n, MOD);
38         while (p > 0) {
39             if (p & 1LL) res = res * base; // multiply when bit is 1
40             base = base * base;            // square each step
41             p >>= 1LL;                     // shift to next bit
42         }
43         return res;
44     }
45 };
46 
47 int main() {
48     ios::sync_with_stdio(false);
49     cin.tie(nullptr);
50 
51     // Example: raise a 3x3 matrix to the 10th power modulo 1e9+7
52     const long long MOD = 1'000'000'007LL;
53     int k = 3; long long n = 10;
54     Matrix A(k, MOD);
55     // Fill A with some values
56     A.a = {
57         {1, 2, 3},
58         {0, 1, 4},
59         {5, 6, 0}
60     };
61 
62     Matrix P = A.pow(n);
63 
64     // Print the result
65     for (int i = 0; i < k; ++i) {
66         for (int j = 0; j < k; ++j) {
67             cout << P.a[i][j] << (j+1==k?'\n':' ');
68         }
69     }
70     return 0;
71 }
72

This program defines a small Matrix class that supports multiplication and fast exponentiation under a modulus. It computes A^{n} using exponentiation by squaring in O(k^{3} log n) time with the standard triple-loop multiply. The example raises a 3×3 matrix to the 10th power modulo 1e9+7 and prints the result.

Time: O(k^3 log n)Space: O(k^2)

Fast Fibonacci F(n) via 2×2 matrix exponentiation (mod 1e9+7)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Mat2 {
5     long long a, b, c, d; // matrix [[a,b],[c,d]]
6     static const long long MOD = 1'000'000'007LL;
7     Mat2(long long a_=1, long long b_=0, long long c_=0, long long d_=1) : a(a_%MOD), b(b_%MOD), c(c_%MOD), d(d_%MOD) {}
8 };
9 
10 Mat2 mul(const Mat2& x, const Mat2& y) {
11     Mat2 r(0,0,0,0);
12     r.a = (x.a*y.a + x.b*y.c) % Mat2::MOD;
13     r.b = (x.a*y.b + x.b*y.d) % Mat2::MOD;
14     r.c = (x.c*y.a + x.d*y.c) % Mat2::MOD;
15     r.d = (x.c*y.b + x.d*y.d) % Mat2::MOD;
16     return r;
17 }
18 
19 Mat2 mpow(Mat2 base, long long n) {
20     Mat2 res; // identity by default
21     while (n > 0) {
22         if (n & 1LL) res = mul(res, base);
23         base = mul(base, base);
24         n >>= 1LL;
25     }
26     return res;
27 }
28 
29 long long fib(long long n) {
30     if (n == 0) return 0;
31     // Transition matrix for Fibonacci
32     Mat2 M(1,1,1,0);
33     Mat2 P = mpow(M, n-1); // M^(n-1)
34     // Then F(n) = P.a * F(1) + P.b * F(0) = P.a * 1 + P.b * 0 = P.a
35     return P.a % Mat2::MOD;
36 }
37 
38 int main(){
39     ios::sync_with_stdio(false);
40     cin.tie(nullptr);
41 
42     long long n; cin >> n; // input n
43     cout << fib(n) << "\n";
44     return 0;
45 }
46

Fibonacci follows the linear rule F(n)=F(n−1)+F(n−2). Using the 2×2 transition matrix [[1,1],[1,0]], the n-th Fibonacci number is read from the powered matrix. This specialized 2×2 code has constant-time multiplication, so the runtime is O(log n).

Time: O(log n)Space: O(1)

General k-term linear recurrence using the companion matrix

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Computes f(n) for a k-term linear recurrence:
5 // f(n) = c1*f(n-1) + c2*f(n-2) + ... + ck*f(n-k)
6 // given coefficients c[0..k-1] = [c1..ck] and initial values f(0..k-1).
7 
8 struct Matrix {
9     int n; long long MOD; vector<vector<long long>> a;
10     Matrix(int n_, long long MOD_, bool ident=false): n(n_), MOD(MOD_) {
11         a.assign(n, vector<long long>(n, 0));
12         if (ident) for (int i=0;i<n;++i) a[i][i]=1%MOD;
13     }
14     static Matrix identity(int n, long long MOD){return Matrix(n, MOD, true);}    
15     Matrix operator*(const Matrix& o) const{
16         Matrix r(n, MOD);
17         for (int i=0;i<n;++i){
18             for (int k=0;k<n;++k){
19                 long long aik=a[i][k]; if (!aik) continue;
20                 for (int j=0;j<n;++j){ r.a[i][j]=(r.a[i][j]+aik*o.a[k][j])%MOD; }
21             }
22         }
23         return r;
24     }
25     Matrix pow(long long p) const{
26         Matrix base=*this, res=Matrix::identity(n, MOD);
27         while(p>0){ if(p&1) res=res*base; base=base*base; p>>=1; }
28         return res;
29     }
30 };
31 
32 long long kth_linear_recurrence(long long n, const vector<long long>& c, const vector<long long>& init, long long MOD){
33     int k = (int)c.size();
34     if (n < (long long)init.size()) return (init[n] % MOD + MOD) % MOD;
35     // Build companion matrix C of size k x k
36     Matrix C(k, MOD);
37     // First row = coefficients c1..ck
38     for (int j=0;j<k;++j){ C.a[0][j] = ((c[j] % MOD) + MOD) % MOD; }
39     // Subdiagonal ones
40     for (int i=1;i<k;++i){ C.a[i][i-1] = 1; }
41 
42     long long power = n - (k - 1);
43     Matrix P = C.pow(power);
44 
45     // Build state vector v(k-1) = [f(k-1), f(k-2), ..., f(0)]^T
46     vector<long long> v(k);
47     for (int i=0;i<k;++i){ v[i] = ((init[k-1-i] % MOD) + MOD) % MOD; }
48 
49     // Multiply P * v
50     vector<long long> res(k, 0);
51     for (int i=0;i<k;++i){
52         __int128 acc = 0;
53         for (int j=0;j<k;++j){ acc += (__int128)P.a[i][j] * v[j]; }
54         res[i] = (long long)(acc % MOD);
55     }
56     // The top entry is f(n)
57     return res[0];
58 }
59 
60 int main(){
61     ios::sync_with_stdio(false);
62     cin.tie(nullptr);
63 
64     // Example: Tribonacci f(n)=f(n-1)+f(n-2)+f(n-3), with f(0)=0,f(1)=0,f(2)=1
65     long long MOD = 1'000'000'007LL;
66     vector<long long> c = {1,1,1};
67     vector<long long> init = {0,0,1};
68 
69     long long n; cin >> n; // query index
70     cout << kth_linear_recurrence(n, c, init, MOD) << "\n";
71     return 0;
72 }
73

This code builds the k×k companion matrix for a k-term linear recurrence and raises it to the appropriate power to jump from the initial block to index n. The state vector is ordered [f(k−1), f(k−2), ..., f(0)]^T so that multiplying by the powered matrix yields f(n) as the top entry. The example configures Tribonacci and answers a query n modulo 1e9+7.

Time: O(k^3 log n)Space: O(k^2)

Counting length-L walks in a directed graph using adjacency matrix powers

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Matrix {
5     int n; long long MOD; vector<vector<long long>> a;
6     Matrix(int n_, long long MOD_, bool ident=false): n(n_), MOD(MOD_) {
7         a.assign(n, vector<long long>(n, 0));
8         if (ident) for (int i=0;i<n;++i) a[i][i]=1%MOD;
9     }
10     static Matrix identity(int n, long long MOD){return Matrix(n, MOD, true);}    
11     Matrix operator*(const Matrix& o) const{
12         Matrix r(n, MOD);
13         for (int i=0;i<n;++i){
14             for (int k=0;k<n;++k){
15                 long long aik=a[i][k]; if (!aik) continue;
16                 for (int j=0;j<n;++j){ r.a[i][j]=(r.a[i][j]+aik*o.a[k][j])%MOD; }
17             }
18         }
19         return r;
20     }
21     Matrix pow(long long p) const{
22         Matrix base=*this, res=Matrix::identity(n, MOD);
23         while(p>0){ if(p&1) res=res*base; base=base*base; p>>=1; }
24         return res;
25     }
26 };
27 
28 int main(){
29     ios::sync_with_stdio(false);
30     cin.tie(nullptr);
31 
32     int n; long long L; long long MOD = 1'000'000'007LL;
33     cin >> n >> L; // number of nodes and walk length
34     Matrix A(n, MOD);
35     int m; cin >> m; // number of directed edges
36     for (int e=0;e<m;++e){
37         int u,v; cin >> u >> v; // 0-indexed nodes
38         A.a[u][v] = (A.a[u][v] + 1) % MOD; // allow multi-edges by counting
39     }
40     int s, t; cin >> s >> t; // query: walks of length L from s to t
41 
42     Matrix P = A.pow(L);
43     cout << P.a[s][t] % MOD << "\n";
44     return 0;
45 }
46

The adjacency matrix A has A_{ij} equal to the count of edges from i to j. The (s,t) entry of A^{L} equals the number of length-L walks from s to t. We raise A to power L with binary exponentiation and read the desired entry modulo 1e9+7 to keep numbers bounded.

Time: O(n^3 log L)Space: O(n^2)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Matrix {
5	int n; // dimension n x n
6	long long MOD; // modulus for arithmetic
7	vector<vector<long long>> a;// matrix data
8
9	Matrix(int n_, long long MOD_, bool ident=false) : n(n_), MOD(MOD_) {
10	a.assign(n, vector<long long>(n, 0));
11	if (ident) {
12	for (int i = 0; i < n; ++i) a[i][i] = 1 % MOD;
13	}
14	}
15
16	static Matrix identity(int n, long long MOD) { return Matrix(n, MOD, true); }
17
18	// Matrix multiplication: C = A * B (mod MOD)
19	Matrix operator*(const Matrix &o) const {
20	Matrix r(n, MOD);
21	// Simple triple-loop; can be optimized by loop reordering or blocking
22	for (int i = 0; i < n; ++i) {
23	for (int k = 0; k < n; ++k) {
24	long long aik = a[i][k];
25	if (aik == 0) continue; // small optimization for sparse rows
26	for (int j = 0; j < n; ++j) {
27	r.a[i][j] = (r.a[i][j] + aik * o.a[k][j]) % MOD;
28	}
29	}
30	}
31	return r;
32	}
33
34	// Fast exponentiation: returns A^p (mod MOD)
35	Matrix pow(long long p) const {
36	Matrix base = *this;
37	Matrix res = Matrix::identity(n, MOD);
38	while (p > 0) {
39	if (p & 1LL) res = res * base; // multiply when bit is 1
40	base = base * base; // square each step
41	p >>= 1LL; // shift to next bit
42	}
43	return res;
44	}
45	};
46
47	int main() {
48	ios::sync_with_stdio(false);
49	cin.tie(nullptr);
50
51	// Example: raise a 3x3 matrix to the 10th power modulo 1e9+7
52	const long long MOD = 1'000'000'007LL;
53	int k = 3; long long n = 10;
54	Matrix A(k, MOD);
55	// Fill A with some values
56	A.a = {
57	{1, 2, 3},
58	{0, 1, 4},
59	{5, 6, 0}
60	};
61
62	Matrix P = A.pow(n);
63
64	// Print the result
65	for (int i = 0; i < k; ++i) {
66	for (int j = 0; j < k; ++j) {
67	cout << P.a[i][j] << (j+1==k?'\n':' ');
68	}
69	}
70	return 0;
71	}
72

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Mat2 {
5	long long a, b, c, d; // matrix [[a,b],[c,d]]
6	static const long long MOD = 1'000'000'007LL;
7	Mat2(long long a_=1, long long b_=0, long long c_=0, long long d_=1) : a(a_%MOD), b(b_%MOD), c(c_%MOD), d(d_%MOD) {}
8	};
9
10	Mat2 mul(const Mat2& x, const Mat2& y) {
11	Mat2 r(0,0,0,0);
12	r.a = (x.ay.a + x.by.c) % Mat2::MOD;
13	r.b = (x.ay.b + x.by.d) % Mat2::MOD;
14	r.c = (x.cy.a + x.dy.c) % Mat2::MOD;
15	r.d = (x.cy.b + x.dy.d) % Mat2::MOD;
16	return r;
17	}
18
19	Mat2 mpow(Mat2 base, long long n) {
20	Mat2 res; // identity by default
21	while (n > 0) {
22	if (n & 1LL) res = mul(res, base);
23	base = mul(base, base);
24	n >>= 1LL;
25	}
26	return res;
27	}
28
29	long long fib(long long n) {
30	if (n == 0) return 0;
31	// Transition matrix for Fibonacci
32	Mat2 M(1,1,1,0);
33	Mat2 P = mpow(M, n-1); // M^(n-1)
34	// Then F(n) = P.a * F(1) + P.b * F(0) = P.a * 1 + P.b * 0 = P.a
35	return P.a % Mat2::MOD;
36	}
37
38	int main(){
39	ios::sync_with_stdio(false);
40	cin.tie(nullptr);
41
42	long long n; cin >> n; // input n
43	cout << fib(n) << "\n";
44	return 0;
45	}
46

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Computes f(n) for a k-term linear recurrence:
5	// f(n) = c1f(n-1) + c2f(n-2) + ... + ck*f(n-k)
6	// given coefficients c[0..k-1] = [c1..ck] and initial values f(0..k-1).
7
8	struct Matrix {
9	int n; long long MOD; vector<vector<long long>> a;
10	Matrix(int n_, long long MOD_, bool ident=false): n(n_), MOD(MOD_) {
11	a.assign(n, vector<long long>(n, 0));
12	if (ident) for (int i=0;i<n;++i) a[i][i]=1%MOD;
13	}
14	static Matrix identity(int n, long long MOD){return Matrix(n, MOD, true);}
15	Matrix operator*(const Matrix& o) const{
16	Matrix r(n, MOD);
17	for (int i=0;i<n;++i){
18	for (int k=0;k<n;++k){
19	long long aik=a[i][k]; if (!aik) continue;
20	for (int j=0;j<n;++j){ r.a[i][j]=(r.a[i][j]+aik*o.a[k][j])%MOD; }
21	}
22	}
23	return r;
24	}
25	Matrix pow(long long p) const{
26	Matrix base=*this, res=Matrix::identity(n, MOD);
27	while(p>0){ if(p&1) res=resbase; base=basebase; p>>=1; }
28	return res;
29	}
30	};
31
32	long long kth_linear_recurrence(long long n, const vector<long long>& c, const vector<long long>& init, long long MOD){
33	int k = (int)c.size();
34	if (n < (long long)init.size()) return (init[n] % MOD + MOD) % MOD;
35	// Build companion matrix C of size k x k
36	Matrix C(k, MOD);
37	// First row = coefficients c1..ck
38	for (int j=0;j<k;++j){ C.a[0][j] = ((c[j] % MOD) + MOD) % MOD; }
39	// Subdiagonal ones
40	for (int i=1;i<k;++i){ C.a[i][i-1] = 1; }
41
42	long long power = n - (k - 1);
43	Matrix P = C.pow(power);
44
45	// Build state vector v(k-1) = [f(k-1), f(k-2), ..., f(0)]^T
46	vector<long long> v(k);
47	for (int i=0;i<k;++i){ v[i] = ((init[k-1-i] % MOD) + MOD) % MOD; }
48
49	// Multiply P * v
50	vector<long long> res(k, 0);
51	for (int i=0;i<k;++i){
52	__int128 acc = 0;
53	for (int j=0;j<k;++j){ acc += (__int128)P.a[i][j] * v[j]; }
54	res[i] = (long long)(acc % MOD);
55	}
56	// The top entry is f(n)
57	return res[0];
58	}
59
60	int main(){
61	ios::sync_with_stdio(false);
62	cin.tie(nullptr);
63
64	// Example: Tribonacci f(n)=f(n-1)+f(n-2)+f(n-3), with f(0)=0,f(1)=0,f(2)=1
65	long long MOD = 1'000'000'007LL;
66	vector<long long> c = {1,1,1};
67	vector<long long> init = {0,0,1};
68
69	long long n; cin >> n; // query index
70	cout << kth_linear_recurrence(n, c, init, MOD) << "\n";
71	return 0;
72	}
73