【旧文补档】矩阵学习笔记
2019/10/12
本文最后修改于 2033 天前,请注意文章内容的时效性。
前言
矩阵是线性代数的内容,在 OI 竞赛中有广泛运用。
常见知识点:
- 矩阵乘法
- 矩阵快速幂
- 矩阵加速递推
定义
- 矩阵: 类似一个
的二维数组。 - 方阵: 一个
的矩阵。 - 矩阵乘法: 将一个
的矩阵 和一个 的矩阵 相乘,得到一个 的矩阵 。
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 项
定义
则
可推出
由矩阵的定义可得到
然后就可以用矩阵快速幂愉快地加速啦^_^
Fibbonacci 前 n 项和
定义
则
定义
则
可推得
由矩阵定义可得
其他
待补充我还不会
加载评论中……