矩阵乘法

IRipple · 2018-05-30 00:15:37 · 个人记录

这篇是给矩阵快速幂做基础的文章，我们来聊聊矩阵乘法。

先看看啥是个矩阵：

↑ 就是这个玩意，和二维数组看起来没什么区别

两个维度记录信息显然，这个家伙比一维要强

之后我们略过一些数学内容，直接来看矩阵乘法

这是两个矩阵，他们的乘法就是红框勾出部分的各项的乘积。

啊举个栗子

ans 11= (a 11×b 11)+ (a 12×b 21)+ (a 13×b 31)

没错很重要的一点就是：矩阵乘法的结果还是矩阵

大概原理如图：

上图所给的是最基本的情况，长和宽相同

那么一般情况呢？

不难想，我们可以得知最基本的一点：

a矩阵的行数=b矩阵的列数

还有一点，

对于结果矩阵：ans行数=a行数 ans列数=b列数

代码举例子（来自p1962）

struct mmp{
    int n,m;//行，列
    long long num[10][10];//每个位置上的数字
    mmp operator *(const mmp &b)//重载运算符（矩阵相乘）
    {
        mmp c;
        c.n=n;//结果矩阵：ans行数=a行数
        c.m=b.m;//结果矩阵：ans列数=b列数
        memset(c.num,0,sizeof(c.num));
        for(int i=1;i<=n;i++)
        for(int j=1;j<=b.m;j++)
        for(int k=1;k<=m;k++)
        c.num[i][j]=(c.num[i][j]+(num[i][k]%mod*b.num[k][j]%mod))%mod;//矩阵乘法
        return c;
    }
};

核心内容到此结束。

但我们就还可以掌握一项技能：

猜矩阵

比如拿dp题目来说，每个题都会有他固定的状态转移方程

那么我们需要做的就是去猜 此状态=前一状态*【猜测的矩阵】

比如P1962斐波那契

这个技巧需要反推的思路，实战分析请参照我的blog中P1962的题解