Matrix Exponentiation — Fast Linear Recurrences

Fibonacci example

// [[1,1],[1,0]]^n · [F1, F0]^T = [F_{n+1}, F_n]^T
long[][] matPow(long[][] M, long n) {
  int k = M.length;
  long[][] result = identity(k);
  while (n > 0) {
    if ((n & 1) == 1) result = mul(result, M);
    M = mul(M, M);
    n >>= 1;
  }
  return result;
}

Generic recurrence

a_n = sum c_i · a_{n-i} → k×k companion matrix. Row 0 = coefficients. Rest = shifted identity.

Complexity

O(k³ log N). Beats O(N·k) direct DP for large N.

Modular

All operations mod p. Standard for combinatorics problems (Fibonacci mod 10^9+7).