Matrix Exponentiation

Matrix exponentiation repeatedly applies one fixed linear transition in logarithmically many compositions. Binary exponentiation works because matrix multiplication is associative and a square identity exists, even though multiplication is not commutative. It is useful for small-state linear recurrences and fixed-length walk counts with huge step counts. We implement generic square multiplication/powering and apply it to Fibonacci modulo a fixed prime.

Prerequisites: Matrix Multiplication; Binary Exponentiation; Fibonacci recurrence.

Build the idea

1. 1. Choose a state vector

   For Fibonacci, use column state [Fᵢ₊₁,Fᵢ]. Multiplying by T=[[1,1],[1,0]] produces [Fᵢ₊₁+Fᵢ,Fᵢ₊₁]=[Fᵢ₊₂,Fᵢ₊₁]. Thus T encodes exactly one recurrence step. Writing the state order first prevents reversing coefficients or reading the wrong result entry.

   $$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}{F}_{i+1}\\ F_i\end{array}\right]=\left[\begin{array}{c}{F}_{i+2}\\ F_{i+1}\end{array}\right]$$

2. 2. Exponentiate using the identity

   Initialize result to identity and repeatedly square T. If the current exponent bit is set, append that power through result=result·base. Squaring base and halving exponent preserve the usual binary-power invariant. Only powers of the same fixed matrix appear, so the standard algorithm does not assume arbitrary unrelated matrices commute.

3. 3. Read Fibonacci directly from a power

   Tⁿ has top-right entry Fₙ for n≥1, and identity at n=0 also has top-right zero. This avoids defining F₋₁ in code. For n=10, T¹⁰=[[89,55],[55,34]], so the answer is 55. The input can be as large as 10^18 because only about 60 squaring steps are needed.

4. 4. Generalize to k-term recurrences

   For xₙ=c₁xₙ₋₁+…+cₖxₙ₋ₖ, choose the ordered vector of k most recent values. The first transition row contains coefficients; lower rows shift each coordinate into the next position. Constant terms can be handled by adding a permanent coordinate one. A small fixed state dimension is important: cubing k can dominate logarithmic exponent savings.

5. 5. Preserve arithmetic and allocation assumptions

   All entries stay normalized modulo 1000000007 and each product is reduced during accumulation. Multiplication creates a fresh output matrix, so it is safe to square a matrix without overwriting values still needed. Memory is O(k²) even though several constant-number temporary matrices may coexist; there is no recursion over the exponent here.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
using ll=long long;
using Matrix=std::vector<std::vector<ll>>;
const ll MOD=1000000007;
Matrix multiply(const Matrix&a,const Matrix&b){
    int k=(int)a.size();
    Matrix c(k,std::vector<ll>(k,0));
    for(int i=0;i<k;++i){
        for(int t=0;t<k;++t){
            for(int j=0;j<k;++j){
                c[i][j]=(c[i][j]+a[i][t]*b[t][j])%MOD;
            }
        }
    }
    return c;
}
Matrix power(Matrix base,unsigned long long exponent){
    int k=(int)base.size();
    Matrix result(k,std::vector<ll>(k,0));
    for(int i=0;i<k;++i){
        result[i][i]=1;
    }
    while(exponent>0){
        if(exponent&1ULL){
            result=multiply(result,base);
        }
        base=multiply(base,base);
        exponent>>=1;
    }
    return result;
}
int main(){
    unsigned long long n;
    std::cin>>n;
    Matrix transition{{1,1},{1,0}},answer=power(transition,n);
    std::cout<<answer[0][1]<<'\n'; // F_n, including F_0=0 from the identity.
}

Complexity analysis

Standard k×k matrix multiplication costs O(k³), so powering costs O(k³ log(n+1)) time and O(k²) memory. For Fibonacci k=2 is constant, giving O(log(n+1)) time/O(1) matrix storage. Reading exponent n≤10^18 uses unsigned long long; output is a residue, not an exact huge Fibonacci integer.

Example input and output

Read n in 0..10^18. Print F_n modulo 1000000007 with F_0=0,F_1=1.

Input

10

Output

55

The top-right entry of [[1,1],[1,0]]¹⁰ is F_10=55.

Practical applications

Use for linear recurrences, fixed automaton transitions and walk counts over huge lengths. Direct DP is simpler for small n. Fibonacci has specialized fast-doubling identities with smaller constants; arbitrary recurrences may not share that special structure.

Check your understanding

What matrix represents applying a square transformation zero times?

Put it into practice

Build a three-coordinate transition for Tribonacci numbers.