kkogoro

矩阵模板
矩阵模板矩阵​ “数学上,一个m×n的矩阵是一个由m行(row)n列(column)元素排列成的矩形阵列。矩...
扫描右侧二维码阅读全文
22
2018/12

矩阵模板

矩阵模板

矩阵

“数学上,一个m×n的矩阵是一个由m行(row)n列(column)元素排列成的矩形阵列。矩阵里的元素可以是数字、符号或数学式”


行列都为 $n$ 的矩阵可以成为 $n$ 维矩阵或方阵

矩阵的运算

矩阵加法

​ 两个大小相同的矩阵对应位置相加

矩阵减法

​ 两个大小相同的矩阵对应位置相减

矩阵数乘

​ 矩阵乘以一个数字(标量),对应位置的元素乘以数字(标量)

矩阵乘法

​ 相乘的两个矩阵必须满足第一个矩阵的列数(column)与第二个矩阵的行数(row)相等,强调先后是因为矩阵乘法不满足交换律

​ 设第一个矩阵为 $A_{p,m}$ , 第二个矩阵为 $B_{m,q}$ 则结果矩阵为 $C_{p,q}$ (注意 $C$ 的大小),运算表达式为

$$ C_{i,j}=\sum_{k=1}^{m}A_{i,k}\times B_{k,j},\space\space\space (i\in[1,p],\space j\in [1,q]) $$

​ 即 $C_{i,j}$ 是由 $A$ 的第 $i$ 的 $m$ 个元素与 $B$ 的第 $j$ 列的 $m$ 个元素分别相乘再相加得到的

​ 矩阵乘法满足结合律 ,即 $(A\times B)\times C=A\times(B\times C)$

​ 矩阵乘法满足左分配律和右分配律 $(A+B)\times C=A\times C + B\times C$ , $C\times(A+B)=C\times A+C\times B$

矩阵转置

​ $m\times n$矩阵 $A$ 的转置是一个 $n\times m$ 的矩阵,记为 $A^{T}$(有些书中也记为 $A^{tr}$ 或 $^tA$ 、$A'$),其中的第 $i$ 个行矢量是原矩阵 $A$ 的第 $i$ 个列矢量;或者说,转置矩阵 $A^{T}$ 第 $i$ 行第 $j$ 列的元素是原矩阵 $A$ 第 $j$ 行第 $i$ 列的元素,
$(A^{T})_{i,j} = A_{j,i}$ ,

满足分配律 $(A+B)^{T}=A^{T}+B^{T}$


矩阵快速幂

​ 对于大小为 $1\times n$ 的矩阵进行状态转移 $T$ 次,时间复杂度是 $O(n^{3}\times \log T)$

​ 状态矩阵即使是多维也最好压成一维,如果有加常数则附加一个 $1$ 元素,转移矩阵里配上系数

​ 如果有求和需求就多一维记 $sum$ ,转移由每个元素向下个 $sum$ 配系数 $1$

​ 如果存在多组询问,则可以预处理出转移矩阵的 $2$ 次幂,然后用初始的 $1\times n$ 矩阵去逐个乘上 $T$ 对应的 $2$ 的次幂的矩阵,由于有一个矩阵是向量,所以单次乘的复杂度是 $O(n^2)$ ,则q次询问的复杂度 $O(qn^{2}\log T)$ ,预处理复杂度 $O(n^{3}\log \text{MAX_T})$


三角矩阵

​ 如果一个方阵只有主对角线上的元素不是0,其它都是0,那么称其为对角矩阵。如果主对角线上方的元素都是0,那么称为下三角矩阵;反之如果主对角线下方的元素都是0,那么称为上三角矩阵。

技巧:压缩储存三角矩阵,对称矩阵;用三元组表示稀疏矩阵的非零位置

矩阵与矢量

​ 行数是1或列数是1的矩阵又可分别称为行矢量和列矢量。这是因为一个矢量可以表示成行数或列数是1的矩阵形式。


代码

洛谷P1939

#include <iostream>
#include <cstdio>
#include <cstring>


const int MOD = 1000000007;


typedef long long LL;


struct Matrix {
    int data[3][3];
    int n, m;
    Matrix() {n = m = 0; memset(data, 0, sizeof data);}
    Matrix(int n, int m) : n(n), m(m) {memset(data, 0, sizeof data);}
    inline void turnV() {
        memset(data, 0, sizeof data);
        for (int i = 0; i < n; ++i) data[i][i] = 1;
        return;
    }
    Matrix operator + (const Matrix &tmp) const {
        Matrix ret = *this;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                ret.data[i][j] = ((LL)ret.data[i][j] + tmp.data[i][j]) % MOD;
            }
        }
        return ret;
    }
    Matrix operator * (const Matrix &tmp) const {
        Matrix ret(n, tmp.m);
        for (int i = 0; i < n; ++i) {
            for (int k = 0; k < m; ++k) {
                if (data[i][k] == 0) continue;
                for (int j = 0; j < tmp.m; ++j) {
                    ret.data[i][j] = ((LL)ret.data[i][j] + (LL)data[i][k] * tmp.data[k][j]) % MOD;
                }
            }
        }
        return ret;
    }
    void operator *= (const Matrix &tmp) {
        *this = *this * tmp;
        return;
    }
    Matrix operator ^ (int k) {
        Matrix method = *this;
        Matrix ret(n, m);
        ret.turnV();
        while (k) {
            if (k & 1) ret *= method;
            k >>= 1;
            method *= method;
        }
        return ret;
    }
    void operator ^= (const int &k) {
        *this = *this ^ k;
        return;
    }
    inline void OutPut() {
        for (int i = 0; i < n; ++i) {
            std::cout << "Matrix :" << std::endl;
            for (int j = 0; j < m; ++j) {
                std::cout << data[i][j] << " " << std::endl;
            }    
        }
        return;
    }
};



int main() {
    Matrix start(1, 3);
    Matrix method(3, 3);
    for (int i = 0; i < 3; ++i) {
        start.data[0][i] = 1;    
    }
    method.data[0][0] = method.data[0][2] = method.data[1][0] = method.data[2][1] = 1;
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        if (n <= 3) printf("1\n");
        else printf("%d\n", (start * (method ^ (n - 3))).data[0][0]);
    }
    return 0;
}
Last modification:April 30th, 2019 at 10:57 pm

Leave a Comment