今天机房里一些人被刷了一下 D 盘，还好我昨天备份了一下 qwq

但是恢复备份用了我几十分钟，这电脑是真的 傻逼....

上午讲 $KMP$ 、$Tire$ 、$AC$ 自动机，过去听了个 $AC$ 自动机就溜了，什么马拉车对我来说都不重要 qwq

讲座中又提到了矩阵乘法，老师甚至觉得矩阵乘法比 $AC$ 自动机更基础 QAQ，我太菜了.....

笔记

矩阵乘法

众所周知，做矩阵乘法有一些规定，若矩阵 $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)$ 。

代码有时间在写....

#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