笔记

矩阵乘法

~~众所周知~~，做矩阵乘法有一些规定，若矩阵 $C = A \times B$，则：

$A$ 的列数必须和 $B$ 的行数相等
若 $A$ 为 $n \times p$ 的矩阵，$B$ 为 $p \times m$ 的矩阵，那么 $C$ 为 $n \times m$ 的矩阵
对于 $C$ 中每一个数，$C_{i,j} = \sum\limits_{k=1}^{p} a_{i,j} \times b_{i,j}$ 。通俗一点来说就是 $C$ 中的第 $i$ 行第 $j$ 列的值为 $A$ 中第 $i$ 行中每一个对应的值与 $B$ 中第 $j$ 列每一个对应的值之积的和。

有一个一本通上的例子：

$$ \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix} \times \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} = \begin{bmatrix} 1 \times 1 + 4 \times 4 & 1 \times 2 + 4 \times 5 & 1 \times 3 + 4 \times 6 \\ 2 \times 1 + 5 \times 4 & 2 \times 2 + 5 \times 5 & 2 \times 3 + 5 \times 6 \\ 3 \times 1 + 6 \times 4 & 3 \times 2 + 6 \times 5 & 3 \times 3 + 6 \times 6 \end{bmatrix} = \begin{bmatrix} 17 & 22 & 27 \\ 22 & 29 & 36 \\ 27 & 36 & 45 \end{bmatrix} $$

反正差不多就酱紫，对应的行和列上每一个数的乘积之和就是答案 qwq

例题

$Fibonacci$ 第 $n$ 项的值

这是一本通上的例题 qwq

这题朴素算法最快到 $O(n)$ ，但是如果当 $1 \leq n \leq 2 \times 10 ^9$ 的时候，就连 $O(n)$ 都跑不过了。我太菜了，暂时不会推出矩阵乘法，所以就先记下过程找找感觉：

因为，

$$ f[i] = 1 \times f[i - 1] + 1 \times f[i - 2] \\ f[i - 1] = 1 \times f[i - 1] + 0 \times f[i - 2] $$

所以，递推式可以转化为矩阵乘法：

$$ \begin{pmatrix} f[i] \\ f[i - 1] \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0\end{pmatrix} \times \begin{pmatrix} f[i - 1] \\ f[i - 2]\end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0\end{pmatrix}^{2} \times \begin{pmatrix} f[i - 2] \\ f[i - 3]\end{pmatrix} \\ \begin{pmatrix} f[n + 1] \\ f[n] \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0\end{pmatrix}^{n - 1} \times \begin{pmatrix} f[2] \\ f[1] \end{pmatrix} $$

这个时候矩阵快速幂就出来了，所以时间复杂度为 $O( \log n) $ 。

~~代码有时间在写....~~

$Code$：

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

using namespace std;
const int MAXN = 2;
const int Mod = 1e9 + 7;

struct Node {
    long long g[MAXN + 5][MAXN + 5];
};
Node f, temp;

long long n, ans;

inline void MatrixInit (Node &x) {
    for (int i = 1; i <= MAXN; i++) {
        for (int j = 1; j <= MAXN; j++) {
            if (i == j) x.g[i][j] = 1LL;
            else x.g[i][j] = 0LL;
        }
    }
    return;
}

inline void MatrixX (Node &x, Node &y, Node &z) {
     memset (z.g, 0, sizeof (z.g));
     
     for (int i = 1; i <= MAXN; i++) {
         for (int j = 1; j <= MAXN; j++) {
             if (!x.g[i][j]) continue;
             for (int k = 1; k <= MAXN; k++) {
                 z.g[i][k] += x.g[i][j] * y.g[j][k];
                 z.g[i][k] %= Mod;
             }
         }
     }
     return;
}

inline void Pow (long long m) {
    MatrixInit (temp);
    Node res = f, t;
    while (m >= 1) {
        if (m & 1) {
            MatrixX (temp, res, t);
            temp = t;
        }
        MatrixX (res, res, t);
        res = t;
        m >>= 1;
    }
    return;
}

long long solve () {
    if (n <= 2) return 1;
    Pow (n - 2);
    long long ans = temp.g[1][1] * 1 + temp.g[2][1] * 1;
    ans %= Mod;
    return ans;
}

int main() {
    scanf ("%lld", &n);
    f.g[1][1] = 1;
    f.g[1][2] = 1;
    f.g[2][1] = 1;
    f.g[2][2] = 0;
    printf ("%lld\n", solve());
    return 0;
}

$Fibonacci$ 求前 $n$ 项和

设 $s[i]$ 表示前 $i$ 项和，

因为，

$$ s[n] = 1 \times s[n - 1] + 1 \times f[n] + 0 \times f[n - 1] \\ f[n + 1]= 0 \times s[n - 1] + 1 \times f[n] + 1 \times f[n - 1] \\ f[n] = 0 \times s[n - 1] + 1 \times f[n] + 0 \times f[n - 1] $$

所以，

$$ \begin{pmatrix} s[n] \\ f[n + 1] \\ f[n] \end{pmatrix} = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{pmatrix} \times \begin{pmatrix} s[n - 1] \\ f[n] \\ f[n - 1] \end{pmatrix} $$

然后再套入通项公式即可。

~~代码依然懒得打....~~

总结

希望矩阵乘法不会考的太难，一般转化的做法就是把需要求的东西，往式子里面套，前面的系数一般都为 0 或 1 。然后就出来了？？（雾）

$AC$ 自动机

这个知识点也是在很久很久以前就咕咕咕了 qwq

本文作者：Snowflake_Pink
本文链接：https://snowflake.pink/archives/81/
最后修改时间：2020-04-14 09:04:22
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！

评论会由可爱的 AI 来审核鸭~

评论列表

暂无评论