首页 > 笔记 > 矩阵乘法总结

矩阵乘法总结


矩阵是什么呢

矩阵大概就是二维数组存储的样子,然后每一个地方都有元素。

例如:

\begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n}\\
a_{21} & a_{22} & \cdots & a_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{m1} & a_{m2} & \cdots & a_{mn}\\
\end{bmatrix}

然后是矩阵的乘法

设¥A¥为¥m \times p¥的矩阵,¥B¥为¥p \times n¥的矩阵,那么称¥m \times n¥的矩阵¥C¥为矩阵¥AB¥的乘积,也就是¥C=AB¥,矩乘规则如下

$$(AB)_{ij}=\sum_{k=1}^p a_{ik} b_{kj} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{ip}b_{pj}$$

注意仅当矩阵A的列数等于矩阵B的行数时,A与B可以相乘。

那么什么是矩阵快速幂呢?

就是把快速幂套到矩阵中,因为矩阵有乘法结合律。(具体见线性代数那个总结)

我们来看一个模版题

luogu3390

这是个模版,顺便练练重载

矩乘的一大用处就是优化递推了啊

矩乘是怎么优化递推的呢?

按照我的理解,递推肯定是从某个初始值推出来的,矩乘就是把我们第一项需要计算多少次算出来,然后直接乘上。

比如我们举个栗子:斐波那契数列

这应该是最经典的递推式了

$$f[i]=f[i-1]+f[i-2],f[0]=0,f[1]=1$$

考虑如何矩乘

对于这一类问题,我们先看一下它是由哪几项推出来的,对于斐波那契,它就是由$f[i-1],f[i-2]$两项推出的,那我们就考虑一下

\begin{align*}
A=\begin{bmatrix}
f_i\\
f_{i+1}\\
\end{bmatrix}
B=\begin{bmatrix}
f_{i+1}\\
f_{i+2}\\
\end{bmatrix}
\end{align*}

如何从A转移到B

我们可以构造一个矩阵

\begin{bmatrix}
a & b\\
c & d\\
\end{bmatrix}

使得

\begin{align*}
\begin{bmatrix}
f_i\\
f_{i+1}\\
\end{bmatrix}
\times \begin{bmatrix}
a & b\\
c & d\\
\end{bmatrix}
=\begin{bmatrix}
f_{i+1}\\
f_{i+2}\\
\end{bmatrix}
\end{align*}

\begin{align*}
\left\{
\begin{aligned}
f_i \times a + f_{i+1} \times b = f_{i+1} \\
f_i \times c + f_{i+1} \times d = f_{i+2} \\
\end{aligned}
\right.
\end{align*}

求解一下就得到

\begin{bmatrix}
a=0 & b=1\\
c=1 & d=1\\
\end{bmatrix}

那就非常好写了

例题luogu1962

这只是一种特殊情况,而且上面的方法只只用于比较简单的递推式

我们如何推广一下这个方法呢,我们考虑一个更加一般的式子

$$f_n=8f_{n-3}+3f_{n-2}+f_{n-1}+n^2+n+8$$

我们首先忽略掉常数项,因为常数最多就是在外面加上一行。

然后我们就要构造一个矩阵,就是这样转移

\begin{align*}
\begin{bmatrix}
f_{n-3}\\
f_{n-2}\\
f_{n-1}\\
n^2\\
n\\
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
f_{n-2}\\
f_{n-1}\\
f_{n}\\
(n+1)^2\\
n+1\\
\end{bmatrix}
\end{align*}

但是我们发现不能简单的从¥n^2¥转移到¥(n+1)^2¥,所以我们要拆开,得到¥(n+1)^2=n^2+2n+1¥,所以就成了这样

\begin{align*}
\begin{bmatrix}
f_{n-1}\\
f_{n-2}\\
f_{n-3}\\
n^2\\
2n\\
1\\
n\\
1\\
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
f_{n}\\
f_{n-1}\\
f_{n-2}\\
(n+1)^2\\
2(n+1)\\
1\\
n+1\\
1\\
\end{bmatrix}
\end{align*}

这里有一个非常需要注意的一点!就是$n^2$展开式的¥2n¥需要单独算!不能共用!因为这是两个不同的式子,它们各自的次数都是不一样的!

推一下

\begin{matrix}
& f_{n} & f_{n-1} & f_{n-2} & (n+1)^2 & 2(n+1) & 1 & n+1 & 1\\
f_{n-1} & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
f_{n-2} & 3 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
f_{n-3} & 8 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
n^2 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
2n & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0\\
n & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
1 & 0 & 0 & 0 & 0 & 2 & 0 & 1 & 1\\
\end{matrix}

然后就可以轻松加个常数

\begin{matrix}
& f_{n} & f_{n-1} & f_{n-2} & (n+1)^2 & 2(n+1) & 1 & n+1 & 1 & 8\\
f_{n-1} & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
f_{n-2} & 3 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
f_{n-3} & 8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
n^2 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
2n & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0\\
n & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
1 & 0 & 0 & 0 & 0 & 2 & 0 & 1 & 1 & 0\\
8 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
\end{matrix}

接下来我要好好讲一下关于统计答案

我们看到这个递推式需要用到前三项的内容,所以我们对于转移矩阵需要跑它的$n-3$次方来记录它的次数。

这样我们就得到了一个矩阵,如何统计答案呢?其实现在的矩阵其实是一个次数矩阵,没有实际的值。比如这是矩阵的二次方:

第一行的4就表示了$f_3$计算了4次,依次类推。

现在就有个很严重的问题,¥n¥的初始值定什么好。

类比一下¥f_n¥的初始值,我们可以发现其实¥n¥在表示的时候就是3+1

假如不能理解的话可以形象的想一下,现在它会给我们$f_1,f_2,f_3$,就表示前三项已经推完了,所以现在我们就是表示第四项每一个值计算了多少次,于是¥n=4¥。

所以最终统计答案的语句

给一个代码:

再来个裸题:nyoj301

不得不说这个网站做得非常辣鸡,卡死了

描述

给你一个递推公式:

$$f(x)=a \times f(x-2)+b \times f(x-1)+c$$

并给你f(1),f(2)的值,请求出f(n)的值,由于f(n)的值可能过大,求出f(n)对1000007取模后的值。

注意:-1对3取模后等于2

输入

第一行是一个整数T,表示测试数据的组数(T<=10000)
随后每行有六个整数,分别表示f(1),f(2),a,b,c,n的值。
其中0<=f(1),f(2)<100,-100<=a,b,c<=100,1<=n<=100000000 (10^9)

输出

输出f(n)对1000007取模后的值

样例输入

2
1 1 1 1 0 5
1 1 -1 -10 -100 3

样例输出

5
999896

这个矩阵是非常好想的

\begin{matrix}
& f_{n} & f_{n-1} & 1\\
f_{n-1} & b & 1 & 0\\
f_{n-2} & a & 0 & 0\\
1 & 1 & 0 & 1\\
\end{matrix}

然后注意一下取模。丧心病狂

未完待续


2 COMMENTS

  1. attack2017-10-25 下午4:27

    “然后就可以轻松加个常数”
    这句话是怎么体现的呢??

    • 远航之曲2017-10-27 下午9:09

      在矩阵外加上一行一列,只转移这个常数就可以了

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×