【旧文补档】矩阵学习笔记

本文发布于 1935 天前，其中的信息可能已经有所发展或是发生改变。

前言

矩阵是线性代数的内容，在OI竞赛中有广泛运用。

常见知识点：

矩阵乘法
矩阵快速幂
矩阵加速递推

定义

矩阵: 类似一个$r * c$的二维数组。
方阵: 一个$n * n$的矩阵。
矩阵乘法: 将一个$a * c$的矩阵$A$和一个$c * b$的矩阵$B$相乘，得到一个$a * b$的矩阵$C$。$C_{i,j} = \sum{A_{i, k} * B_{k, j}}$

C++定义

#include <bits/stdc++.h>
using namespace std;
struct matrix {
private:
	int **a; // 二维数组指针
	int r, c; // r * c 矩阵
public:
	matrix(int m, int n) {
		r = m;
		c = n;
		a = new int*[r]; // 动态二维数组
		for (int i = 0; i < r; i++) {
			a[i] = new int[c];
			for (int j = 0; j < c; j++) {
				a[i][j] = 0;
			}
		}
	}
	int& at(const int &x, const int &y) {
		return a[x][y];
	}
	int& row() {
		return r;
	}
	int& cal() {
		return c;
	}
	// 重载赋值运算符
	void operator=(matrix M) {
		r = M.row();
		c = M.cal();
		a = new int*[r];
		for (int i = 0; i < r; i++) {
			a[i] = new int[c];
			for (int j = 0; j < c; j++) {
				a[i][j] = M.at(i, j);
			}
		}
	}
	// 重载矩阵乘法
	matrix operator*(matrix &M) {
		matrix t(r, M.cal());
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < M.cal(); j++) {
				int p = 0;
				for (int o = 0; o < c; o++) {
					p += a[i][o] * M.at(o, j);
				}
				t.at(i, j) = p;
			}
		}
		return t;
	}
	// 输出矩阵
	void print() {
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				printf("%d ", a[i][j]);
			}
			printf("\n");
		}
	}
};
// 矩阵快速幂
matrix quickpow(matrix mat, int n) {
	matrix base = mat, ans = mat;
	--n;
	while (n) {
		if (n & 1) {
			ans = ans * base;
			--n;
		}
		base = base * base;
		n >>= 1;
	}
	return ans;
}

用途

加速递推

比如Fibonacci的递推就可以用这个加速。

Fibonacci第n项

定义$f(n)$为$Fibonacci$数列的第$n$项。

则$f(n) = f(n – 1) + f(n – 2)$

$f(1) = 1, f(2) =1$

可推出

$f(n) = 1 * f(n – 1) + 1 * f(n – 2)$

$f(n – 1) = 1 * f(n – 1) + 0 * f(n – 2)$

由矩阵的定义可得到

$$\begin{bmatrix} S(n) \\ f(n) \\ f(n – 1) \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix} * \begin{bmatrix} S(n – 1) \\ f(n – 1) \\ f(n – 2) \end{bmatrix} \Rightarrow \begin{bmatrix} S(n) \\ f(n) \\ f(n – 1) \end{bmatrix} = {\begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix}}^{n – 2} * \begin{bmatrix} f(1) \\ f(2) \\ f(1) \end{bmatrix}$$

然后就可以用矩阵快速幂愉快地加速啦^_^

Fibbonacci前n项和

定义$f(n)$为$Fibonacci$数列的第$n$项。

则$f(n) = f(n – 1) + f(n – 2)$

$f(1) = 1, f(2) =1$

定义$S(n)$为$Fibonacci$数列前$n$项之和。

则$S(n) = f(1) + f(2) + \cdots + f(n) = S(n – 1) + f(n)$

可推得

$S(n) = S(n – 1) + f(n) = 1 * S(n – 1) + 1 * f(n – 1) + 1 * f(n – 2)$

$f(n) = 0 * S(n – 1) + 1 * f(n – 1) + 1 * f(n – 2)$

$f(n – 1) = 0 * S(n – 1) + 1 * f(n – 1) + 0 * f(n – 2)$

由矩阵定义可得

其他

待补充~~我还不会~~