Exponenciación de matrices

Recursos
Fuente	Recurso	Notas
CP2	5.9 - Powers of a Square Matrix
CPH	23 - Matrices
CF	Errichto - Matrix Exponentiation	video + conjunto de problemas
CF	Cool tricks using Matrix Exponential	aplicaciones interesantes de la exponenciación de matrices
Mostafa	Matrix Power Applications	presentación de exponenciación de matrices

Ejemplo - Fibonacci

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Fibonacci Numbers	Fácil	Matrix, Exponentiation	—

Los números de Fibonacci se definen de la siguiente forma:

\begin{align*} F_0 &= 0 \\ F_1 &= 1 \\ F_{n+1} &= F_{n} + F_{n-1} \end{align*}

También podemos escribirlos usando la siguiente recurrencia matricial:

A = \begin{bmatrix}1&1\\1&0\end{bmatrix}^n=\begin{bmatrix}F_{n+1} & F_n \\ F_n & F_{n-1}\end{bmatrix}

Demostración por inducción

Caso base ( $n=1$ ):

A^1 = \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix} = \begin{bmatrix}F_2 & F_1 \\ F_1 & F_0\end{bmatrix}

Paso inductivo ( $n+1$ ):

A^{n+1}=A\,A^n=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{bmatrix}=\begin{bmatrix} F_{n+1}+F_n & F_{n}+F_{n-1} \\ F_{n+1} & F_{n} \end{bmatrix}=\begin{bmatrix} F_{n+2} & F_{n+1} \\ F_{n+1} & F_{n} \end{bmatrix}

Con esto, hemos mostrado que la fórmula vale para todo $n \in \mathbb{N}$ .

Implementación

Complejidad temporal: $\mathcal{O}(\log N)$

C++Python


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const ll MOD = 1e9 + 7;
 
using Matrix = array<array<ll, 2>, 2>;
 
Matrix mul(Matrix a, Matrix b) {
	Matrix res = {{{0, 0}, {0, 0}}};
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				res[i][j] += a[i][k] * b[k][j];
				res[i][j] %= MOD;
			}
		}
	}
 
	return res;
}
 
int main() {
	ll n;
	cin >> n;
 
	Matrix base = {{{1, 0}, {0, 1}}};
	Matrix m = {{{1, 1}, {1, 0}}};
 
	for (; n > 0; n /= 2, m = mul(m, m)) {
		if (n & 1) base = mul(base, m);
	}
 
	cout << base[0][1];
}


from typing import List
 
MOD = 10**9 + 7
 
 
def mul(A: List[List[int]], B: List[List[int]], MOD: int) -> List[List[int]]:
	C = [[0, 0], [0, 0]]
	for i in range(2):
		for j in range(2):
			for k in range(2):
				C[i][j] += ((A[i][k]) * (B[k][j])) % MOD
	return C
 
 
def power(matrix: List[List[int]], n: int) -> List[List[int]]:
	if n == 0:
		return [[1, 0], [0, 1]]
	if n == 1:
		return matrix
	half = power(matrix, n // 2, MOD)
	square = mul(half, half, MOD)
	if n % 2 == 0:
		return square
	return mul(matrix, square, MOD)
 
 
n = int(input())
if n == 0:
	print(0)
elif n > 2:
	o = power([[1, 1], [1, 0]], n - 1)
	print(o[0][0] % MOD)
else:
	print(1)

Encontrar la matriz correcta - Recurrencias lineales generalizadas

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	SPOJ	★ Recursive Sequence	Fácil	Matrix, Exponentiation	—

Podemos generalizar la técnica de arriba para calcular valores en cualquier recurrencia lineal. La parte delicada es encontrar la matriz correcta para el problema. Veamos cómo podemos hallar esta matriz $M$ . Sabemos que debe cumplirse la siguiente ecuación:

\begin{bmatrix} M_{1,1} & M_{1, 2} & \dots \\ \vdots & \ddots & \vdots \\ M_{k, 1} & \dots & M_{k, k} \end{bmatrix} \begin{bmatrix} a_1 \\ \vdots \\ a_k \end{bmatrix} = \begin{bmatrix} a_2 \\ \vdots \\ a_{k + 1} \end{bmatrix}

Aquí usamos los valores de $a_1, \dots, a_n$ para hallar $a_{k+1}$ . También podemos descartar $a_1$ ya que no se usará para calcular $a_{k+2}$ . Si pensamos en la multiplicación de matrices, notamos que hay una diagonal de $1$ s desplazada a la derecha en $1$ porque $a_i \rarr a_{i + 1}$ para $i < k$ . Así que ahora tenemos (usando $k = 5$ como ejemplo):

M = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ M_{5, 1} & M_{5, 2} & M_{5, 3} & M_{5, 4} & M_{5, 5} \end{bmatrix}

Para hallar la fila de abajo, usamos la fórmula de la recurrencia:

M = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ c_5 & c_4 & c_3 & c_2 & c_1 \end{bmatrix}

Con esta $M$ , la ecuación siempre se cumple.

Implementación

Complejidad temporal: $\mathcal{O}(K^3 \log N)$

C++


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MOD = 1e9;
 
template <typename T> void matmul(vector<vector<T>> &a, vector<vector<T>> b) {
	int n = a.size(), m = a[0].size(), p = b[0].size();
	assert(m == b.size());
	vector<vector<T>> c(n, vector<T>(p));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < p; j++) {
			for (int k = 0; k < m; k++) {
				c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
			}
		}
	}
 
	a = c;
}
 
template <typename T> struct Matrix {
	vector<vector<T>> mat;
	Matrix() {}
	Matrix(vector<vector<T>> a) { mat = a; }
	Matrix(int n, int m) {
		mat.resize(n);
		for (int i = 0; i < n; i++) { mat[i].resize(m); }
	}
 
	int rows() const { return mat.size(); }
	int cols() const { return mat[0].size(); }
 
	// makes the identity matrix for a n by n matrix
	void makeiden() {
		for (int i = 0; i < rows(); i++) { mat[i][i] = 1; }
	}
 
	void print() const {
		for (int i = 0; i < rows(); i++) {
			for (int j = 0; j < cols(); j++) { cout << mat[i][j] << ' '; }
			cout << '\n';
		}
	}
 
	Matrix operator*=(const Matrix &b) {
		matmul(mat, b.mat);
		return *this;
	}
 
	Matrix operator*(const Matrix &b) { return Matrix(*this) *= b; }
};
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n, k;
		cin >> k;
		Matrix<ll> mat(k, k), vec(k, 1), cur(k, k);
		cur.makeiden();
		for (int i = 0; i < k; i++) { cin >> vec.mat[i][0]; }
 
		for (int i = 0; i < k; i++) { cin >> mat.mat[k - 1][k - i - 1]; }
 
		for (int i = 1; i < k; i++) { mat.mat[i - 1][i] = 1; }
 
		cin >> n;
		n--;
		while (n > 0) {
			if (n & 1) cur *= mat;
			mat *= mat;
			n >>= 1;
		}
 
		Matrix<ll> res = cur * vec;
		cout << res.mat[0][0] << '\n';
	}
}

Conclusión

La lección aquí no es la matriz exacta usada en las recurrencias lineales, sino el método para derivarla. El proceso de pensar en un vector antes y después de aplicar $M$ , y luego deducir $M$ por lógica, es una técnica que se generaliza mucho más allá de las recurrencias lineales estándar. Por ejemplo, ver si se puede hallar la ecuación necesaria y la matriz correcta (usando $k = 5$ como ejemplo) para resolver esta recurrencia modificada para $i > k$ :

a_i = c_1a_{i-1} + c_2a_{i-2} + ... + c_ka_{i-k} + C

donde $C$ es una constante dada.

Solución

\begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ c_5 & c_4 & c_3 & c_2 & c_1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \\ a_5 \\ C \end{bmatrix} = \begin{bmatrix} a_2 \\ a_3 \\ a_4 \\ a_5 \\ a_6 \\ C \end{bmatrix}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CSES	Graph Paths I	Fácil	Matrix, Exponentiation	—
CSES	Graph Paths II	Fácil	Matrix, Exponentiation	—
CF	Xor-sequences	Fácil	Exponentiation, Matrix	Solución
CF	Sasha and Array	Normal	Exponentiation, Matrix, PURS	Solución
Baltic OI	2007 - Connected Points	Normal	Matrix, Exponentiation	Solución
Balkan OI	★ 2009 - Reading	Normal	Matrix, Exponentiation	Solución
DMOJ	Ray Needs Help	Normal	Matrix, Exponentiation	—
Platinum	COWBASIC	Difícil	Matrix, Exponentiation	—