矩阵

· · 个人记录

矩阵

定义

什么是矩阵运算呢？

在理解这个问题前，我们先要知道什么是矩阵

bdfs (确信) 给的定义如下

矩阵是一个按照长方阵列排列的复数或实数集合

(你管它神马神奇的数呢) 总之，矩阵就是一堆数，按照矩形排列形成的集合

那么，我们所需要记录的也就是它的长、宽以及矩阵中存储的元素 特殊的，长宽相等的矩阵我们定义它为方阵

当两个矩阵的长宽相等时，我们认为这两个矩阵为同型矩形 (这不是全等吗 bushi)

基本运算

矩阵的运算我们可以类比实数的运算来理解

在实数运算中，一般由进行运算的实数和运算符组成，运算符决定了运算类型

那么同样的，矩阵运算也是如此

加法运算

首先，我们来看加法运算

两个矩阵进行一般的加法运算的前提是两个矩阵为同型矩阵

我们只需要将对应位置的元素相加即可，如下图

在矩阵的加法运算中，满足交换律和结合律 (废话)，也就是

A+B=B+A+B=B+A

(A+B)+C=A+(B+C)(A+B)+C=A+(B+C)

也许有人想问了，如果我想让两个非同型矩形进行相加可不可以实现呢？

答案是可以的，这种运算是被支持的，我们称这种运算为直和

但由于这种运算使用较少，且与本文关系不大，我们在此不多做解释

减法运算

在实数运算中，减法为加法的逆运算，同样的，在矩阵运算中也是如此，如下图

数乘

在实数运算中我们并没有数乘这种运算（毕竟本身就是数，直接叫乘法了,典型废话论）

所以在数乘运算中，我们类比向量来进行理解

在数乘向量运算中，只需要将向量中的每个元素乘上那个数就可以了 数乘矩阵也是如此，如图

矩阵乘法（矩阵乘矩阵）

在向量乘向量的运算中，是将每个元素与它对应的元素相乘，求所有乘积之和

那么矩阵乘矩阵是不是就是两个同型矩阵的对应元素相乘呢？(当然bushi)

两个矩阵相乘的前提是前一个矩阵的列数等于后一个矩阵的行数

举个栗子，A为n k矩阵，B为k m矩阵，C为m * n矩阵，那么A可以与B相乘，B可以与C相乘，C可以与A相乘，其他均不成立

我们知道了什么情况下两个矩阵可以相乘，那么他们怎么相乘呢？不讲每个对应位置相乘还能怎么乘呢？

设A为n k矩阵，B为m k矩阵,那么它们的乘积C则为一个n * m矩阵

示例代码：

matrix operator*(const matrix &m1,const matrix &m2){
    matrix m3;
    m3.n=m1.n;m3.m=m2.m;
    for (int i=1;i<=m3.n;i++)
        for (int k=1;k<=m1.m;k++)
            for (int j=1;j<=m3.m;j++)
                m3.z[i][j]+=m1.z[i][k]*m2.z[k][j];
    return m3;
}
/*
以ikj的顺序枚举最快
因为缓存的机制是访问了a[1],系统就将内存中的a全部放入缓存
因为访问缓存比访问内存快
所以这个顺序最快

在矩阵乘法中满足以下运算律：

(AB)C=a(BC)(AB)C=a(BC)

(A+B)C=AC+BC(A+B)C=AC+BC

C(A+B)=CA+CBC(A+B)=CA+CB

矩阵快速幂

这个其实学会了矩阵乘直接重载运算符一样算快速幂即可。

矩阵快速幂代码~

#include<bits/stdc++.h>
using namespace std;
const int Mod=1000000007;
struct Matrix {
    long long c[101][101];
} A,I;
long long n,k;
Matrix operator*(const Matrix &x,const Matrix &y) {
    Matrix a;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            a.c[i][j]=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            for(int k=1; k<=n; k++) {
                a.c[i][j]+=x.c[i][k]*y.c[k][j]%Mod;
                a.c[i][j]%=Mod;
            }
    return a;
}

int main() {
    cin>>n>>k;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cin>>A.c[i][j];
    for(int i=1; i<=n; i++)
        I.c[i][i]=1;
    while(k>0) {
        if(k%2==1) I=I*A;
        A=A*A;
        k=k>>1;
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++)
            cout<<I.c[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}

例题1

P1962肥不拉几序列

这个题最朴素的想法是枚举

但是超时

我们考虑定义一个矩阵，初始2 \times 2 的大小，出了最后一个数全是1。

然后计算这个的 n 的阶乘，就会发现第一行第二个是 f[n]

我们会发现这个规律对于 n=1/2 不成立，记得特判

别忘了取模

例题2

走 k 步走到点n，求方案数

1\leq k\leq10^9 1\leq n\leq 100

用 z[i][j] 记录 i ,j 之间有没有边

1表示有，0表示无

先将走了0步走到的点全部标位0，即 $ f[0][i]=0 $ ,到1标为1 $ f[i][j] = f[i-1][p1] + f[i-1][p2]··· $ $ p $ 是可以直接走到 $ i $ 的点。 $ f[k][n] $ 为答案 时间复杂度$ O(n^2k)

考虑优化

先在 i,j 之间添加一个维度 d ,让其始终为1。

所以式子变成 f[i][d][j] = f[i-1][d][p] \times z[p][j]

我们现在将 f_i 看成一个变量，于是式子成了 f_i[d][j] = f_{i-1}[d][p] \times z[p][j]

于是 f_i = f_{i-1}\times z=f_0 \times z^i

所以题目变成了矩阵快速幂

例题3

P4159迷路

拆边，但复杂度变大，考虑优化

将拆出来的边合并，如图

在不同的地方分出枝，这样 n \leq 100

再按照上一个题的思路就做完了

高斯消元

逆矩阵

定义

设 I 为单位矩阵（相当于数学中的1）

如果 A\times B=I 称 B 为 A 的逆矩阵

我们看成每个位置都是一个方程， B 的每一个位置设未知数，然后列方程，跑高斯消元即可

但是复杂度不太友善的样子，是 O(n^6) （好像只能跑 n\leq 30）

/*
*               ii.                                         ;9ABH,
*              SA391,                                    .r9GG35&G
*              &#ii13Gh;                               i3X31i;:,rB1
*              iMs,:,i5895,                         .5G91:,:;:s1:8A
*               33::::,,;5G5,                     ,58Si,,:::,sHX;iH1
*                Sr.,:;rs13BBX35hh11511h5Shhh5S3GAXS:.,,::,,1AG3i,GG
*                .G51S511sr;;iiiishS8G89Shsrrsh59S;.,,,,,..5A85Si,h8
*               :SB9s:,............................,,,.,,,SASh53h,1G.
*            .r18S;..,,,,,,,,,,,,,,,,,,,,,,,,,,,,,....,,.1H315199,rX,
*          ;S89s,..,,,,,,,,,,,,,,,,,,,,,,,....,,.......,,,;r1ShS8,;Xi
*        i55s:.........,,,,,,,,,,,,,,,,.,,,......,.....,,....r9&5.:X1
*       59;.....,.     .,,,,,,,,,,,...        .............,..:1;.:&s
*      s8,..;53S5S3s.   .,,,,,,,.,..      i15S5h1:.........,,,..,,:99
*      93.:39s:rSGB@A;  ..,,,,.....    .SG3hhh9G&BGi..,,,,,,,,,,,,.,83
*      G5.G8  9#@@@@@X. .,,,,,,.....  iA9,.S&B###@@Mr...,,,,,,,,..,.;Xh
*      Gs.X8 S@@@@@@@B:..,,,,,,,,,,. rA1 ,A@@@@@@@@@H:........,,,,,,.iX:
*     ;9. ,8A#@@@@@@#5,.,,,,,,,,,... 9A. 8@@@@@@@@@@M;    ....,,,,,,,,S8
*     X3    iS8XAHH8s.,,,,,,,,,,...,..58hH@@@@@@@@@Hs       ...,,,,,,,:Gs
*    r8,        ,,,...,,,,,,,,,,.....  ,h8XABMMHX3r.          .,,,,,,,.rX:
*   :9, .    .:,..,:;;;::,.,,,,,..          .,,.               ..,,,,,,.59
*  .Si      ,:.i8HBMMMMMB&5,....                    .            .,,,,,.sMr
*  SS       :: h@@@@@@@@@@#; .                     ...  .         ..,,,,iM5
*  91  .    ;:.,1&@@@@@@MXs.                            .          .,,:,:&S
*  hS ....  .:;,,,i3MMS1;..,..... .  .     ...                     ..,:,.99
*  ,8; ..... .,:,..,8Ms:;,,,...                                     .,::.83
*   s&: ....  .sS553B@@HX3s;,.    .,;13h.                            .:::&1
*    SXr  .  ...;s3G99XA&X88Shss11155hi.                             ,;:h&,
*     iH8:  . ..   ,;iiii;,::,,,,,.                                 .;irHA
*      ,8X5;   .     .......                                       ,;iihS8Gi
*         1831,                                                 .,;irrrrrs&@
*           ;5A8r.                                            .:;iiiiirrss1H
*             :X@H3s.......                                .,:;iii;iiiiirsrh
*              r#h:;,...,,.. .,,:;;;;;:::,...              .:;;;;;;iiiirrss1
*             ,M8 ..,....,.....,,::::::,,...         .     .,;;;iiiiiirss11h
*             8B;.,,,,,,,.,.....          .           ..   .:;;;;iirrsss111h
*            i@5,:::,,,,,,,,.... .                   . .:::;;;;;irrrss111111
*            9Bi,:,,,,......                        ..r91;;;;;iirrsss1ss1111
*/