2019.8.11 集训笔记
浏览 180 | 评论 0 | 字数 3748
Snowflake_Pink
2019年08月11日
  • 今天机房里一些人被刷了一下 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) $ 。

    代码有时间在写....

    $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 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论