定义
我们把一个 \(n \times m\) 的数列叫做矩阵。他可以解决一部分线性递推的题目。特别的,我们常说的向量就是一个 \(1 \times n\) 的矩阵捏。
单位元
我们形如这样 \(\begin{bmatrix} 1&0 &0 \\0 &1 &0\\0&0&1\end{bmatrix}\) 这种只有对角线都是 \(1\) 的叫做单位元。
运算
主要讲一下比较特别的乘法。如果两个矩阵需要相乘,需要满足的必要条件为当一个矩阵的行数等于另一个矩阵的列数。至于加减法,就是对应的减去对应的。
我们令 \(a,b,c\) 为三个 $n\times n $ 的矩阵。令 \(a\) 为矩阵 \(b,c\) 相乘的结果,那么可以写作 $a = bc $。且存在
\[a_{i,j} = \sum_{k=1}^nb_{i,k} \times c_{k,j} \]也就是
\(\begin{bmatrix} a & b \\ c & d\end{bmatrix} \times \begin{bmatrix} e & f\\ g & h\end{bmatrix} = \begin{bmatrix} a\times e +b\times g & a \times f+b \times h \\ c \times e+ d\times g & c \times f+d \times h\end{bmatrix}\)
注意事项:矩阵乘法满足结合律,不满足交换律。
矩阵快速幂(重要!!!)
这玩应,没他就像你没了手一样难受。由于矩阵满足结合律,我们用一种类似快速幂的方法即可。就是把快速幂改为矩阵乘法。
参考代码 。
运用
例题一
存在一个递推式 $F(i) =F(i-1) +F(i-2) \text{且} i \ge 2 $ 。
问你第 \(x\) 项是多少。这玩应,你可能会说递推,但那样太慢了,不妨上矩阵。我们考虑如何把他放入矩阵,首先,要实现矩阵递推,我们需要先有 $ F(i-1) \text{和} F(i-2)$ 这两个东西,所以,我们需要先放入
\(\begin{bmatrix}F(i-1),F(i-2)\end{bmatrix}\) 。然后,考虑递推式,我们还要在矩阵的第一列放一,这样才能相加.然后,第二列第一个是一,这样 $F(i-2) $ 就不会被相加。所以,综上所述,我们构造的矩阵就是
\(\begin{bmatrix} F(i-1) & F(i-2) \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}\) 。最后对他快速幂即可。
标签:begin,end,矩阵,笔记,times,学习,bmatrix,递推 From: https://www.cnblogs.com/zhong114514/p/17378297.html