秋实-Allenyou的小窝

稻花香里说丰年,听取WA声一片

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

2019/10/12

本文最后修改于 1706 天前,请注意文章内容的时效性。

前言

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

常见知识点:

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

定义

  • 矩阵: 类似一个rc的二维数组。
  • 方阵: 一个nn的矩阵。
  • 矩阵乘法: 将一个ac的矩阵A和一个cb的矩阵B相乘,得到一个ab的矩阵CCi,j=Ai,kBk,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(n1)+f(n2)

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

可推出

f(n)=1f(n1)+1f(n2)

f(n1)=1f(n1)+0f(n2)

由矩阵的定义可得到

[S(n)f(n)f(n1)]=[111011010][S(n1)f(n1)f(n2)][S(n)f(n)f(n1)]=[111011010]n2[f(1)f(2)f(1)]

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

Fibbonacci 前 n 项和

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

f(n)=f(n1)+f(n2)

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

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

S(n)=f(1)+f(2)++f(n)=S(n1)+f(n)

可推得

S(n)=S(n1)+f(n)=1S(n1)+1f(n1)+1f(n2)

f(n)=0S(n1)+1f(n1)+1f(n2)

f(n1)=0S(n1)+1f(n1)+0f(n2)

由矩阵定义可得

[S(n)f(n)f(n1)]=[111011010][S(n1)f(n1)f(n2)][S(n)f(n)f(n1)]=[111011010]n2[f(1)f(2)f(1)]

其他

待补充我还不会

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

https://www.allenyou.wang/post/1

本文作者

秋实-Allenyou

授权协议

CC BY-NC-SA 4.0