前言

矩阵是线性代数的内容,在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}f(n)\\f(n - 1)\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix} * \begin{bmatrix}f(n - 1)\\f(n - 2)\end{bmatrix} \Rightarrow \begin{bmatrix}f(n)\\f(n - 1)\end{bmatrix} = {\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n - 2} * \begin{bmatrix}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)$
由矩阵定义可得
$\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}$

其他

待补充我还不会

本文作者:Author:     文章标题:矩阵学习笔记
本文地址:https://www.allenyou.wang/oi/matrix-note.html     
版权说明:若无注明,本文皆为Allenyou's Blog原创,转载请保留文章出处。
Last modification:December 7th, 2019 at 09:56 pm