矩阵(Matrix)定义

一个 $n\times m$ 的矩阵是一个由 $n$ 行 $m$ 列元素排成的矩形阵列。矩阵里的元素可以是数字符号或者数学式。

形如$\left(\begin{matrix}a&b\\c&d\end{matrix}\right)$的数表称为二阶矩阵，它由二行二列组成，其中$a,b,c,d$称为这个矩阵的元素。

形如$\left(\begin{matrix}x_1\\x_2\end{matrix}\right)$的有序对称为列向量(Column Vector)

矩阵加法

矩阵的加法非常简单

对，就是你想的那样

$$\left( \begin{matrix} a_{1,1}&a_{1,2}&\cdots&a_{1,m}\\a_{2,1}&a_{2,1}&\cdots&a_{2,m}\\\vdots&\vdots&&\vdots\\a_{n,1}&a_{n,2}&\cdots&a_{n,m} \end{matrix} \right)\pm \left( \begin{matrix} b_{1,1}&b_{1,2}&\cdots&b_{1,m}\\b_{2,1}&b_{2,1}&\cdots&b_{2,m}\\\vdots&\vdots&&\vdots\\b_{n,1}&b_{n,2}&\cdots&b_{n,m} \end{matrix} \right)= \left( \begin{matrix} a_{1,1}\pm b_{1,1}&a_{1,2}\pm b_{1,2}&\cdots&a_{1,m}\pm b_{1,m}\\a_{2,1}\pm b_{2,1}&a_{2,1}\pm b_{2,2}&\cdots&a_{2,m}\pm b_{2, m}\\\vdots&\vdots&&\vdots\\a_{n,1}\pm b_{n,1}&a_{n,1}\pm b_{n,2}&\cdots&a_{n,m}\pm b_{n,m} \end{matrix} \right)$$

注意：两个矩阵必须为同型矩阵(即必须都是 $n\times m$ 的矩阵)才能相加

并且，矩阵加减法满足交换律和结合律(即$A+B=B+A$，$(A+B)+C=A+(B+C)$)

矩阵乘法

矩阵乘法稍有不同

嗯，真的只有一点不同

如果有矩阵 $A$ 大小为 $n\times m$ ，矩阵 $B$ 大小为 $m\times s$ ，相乘为矩阵 $C$，矩阵 $C$ 的大小一定为 $n\times s$

矩阵乘法遵循 $C=\sum_{k=1}^{m}a_{i,k}b_{k,j}$

嗯，只有一点

举个例子

设

$$\begin{align} A&=\left(\begin{matrix}a&b\\c&d\end{matrix}\right)\\\\ B&=\left(\begin{matrix}x_1\\x_2\end{matrix}\right)\\ \end{align}$$

则

$$\begin{align} C=AB&=\left(\begin{matrix}ax_1+bx_2\\cx_1+dx_2\end{matrix}\right)\\ \end{align}$$

称为二阶矩阵 $A$ 与平面向量 $B$ 的乘积，记为 $AB=C$

利用矩阵求斐波那契(Fibonacci)数列

众所周知，斐波那契数列从第三项开始，每一项都是前两项之和

即$F_n=F_{n-1}+F_{n-2},n\geq3$

特别的$F_0=0,F_1=F_2=1$

把斐波那契数列中相邻的两项( $F_n$ 和 $F_{n-1}$ )写成一个$2\times1$的矩阵

$$\begin{align} &=\left( \begin{matrix} F_n\\ F_{n-1} \end{matrix} \right)\\\\ &=\left( \begin{matrix} F_{n-1}+F_{n-2}\\ F_{n-1} \end{matrix} \right)\\\\ &=\left( \begin{matrix} 1\times F_{n-1}+1\times F_{n-2}\\ 1\times F_{n-1}+0\times F_{n-2} \end{matrix} \right)\\\\ &=\left( \begin{matrix} 1&1\\ 1&0 \end{matrix} \right) \times \left( \begin{matrix} F_{n-1}\\ F_{n-2} \end{matrix} \right)\\\\ &=\left( \begin{matrix} 1&1\\ 1&0 \end{matrix} \right)^{n-1} \times \left( \begin{matrix} F_1\\ F_0 \end{matrix} \right)\\\\ &=\left( \begin{matrix} 1&1\\ 1&0 \end{matrix} \right)^{n-1} \times \left( \begin{matrix} 1\\ 0 \end{matrix} \right) \end{align}$$

求 $F_n$ 等同于求二阶矩阵的 $n-1$ 次方，结果取矩阵第一行元素。

问题转换为二阶矩阵的 $n$ 次幂

求二阶矩阵的 $N$ 次幂

这里可以回顾一下矩阵乘法

假设计算矩阵 $A$ 的 $N$ 次幂

方法一

二阶矩阵的乘法满足结合律

设$A,B,C$都是任意的二阶矩阵

则$A(BC)=(AB)C$

不在此证明

设$n=N\div 2$ (结果向下取整)

若 $N\in 2k$ 则 $A^N=A^n\times A^n$

若 $N\in 2k+1$ 则 $A^N=A^n\times A^n\times A$

这样可以减少计算次数，自行思考原因

方法二

以计算 $A^6$ 为例

例如$6_{(10)}=110_{(2)}$

则 $A^6=A^4\times A^2$

二进制位

上图显示二进制与幂的指数关系

二进位为 1 需要乘，为 0 不需要乘

再例如$7_{(10)}=111_{(2)}$

则$A^7=A^4\times A^2\times A^1$

先随随便便写一个求快速幂的代码(相信大家都会写吧

int qpow(int a, int k) {
    int res = 1;
    while(k) {
        if(a & 1) res *= a;
        k >>= 1;
        a *= a;
    }
    return res;
}

那么到底怎么用矩阵求斐波那契数列呢？

代码

#include<cstdio>
#include<cstring>

struct Matrix {
	long long fib[2][2];
	Matrix() {memset(fib, 0, sizeof fib);}
};

Matrix qmul(Matrix &a, Matrix &b) {
	Matrix c;
	for(int i = 0; i < 2; ++i) {
		for(int j = 0; j < 2; ++j) {
			for(int k = 0; k < 2; ++k) {
				c.fib[i][j] += a.fib[i][k] * b.fib[k][j];
			}
		}
	}
	return c;
}

Matrix qpow(Matrix a, long long k) {
	Matrix ans;
	ans.fib[0][0] = ans.fib[1][1] = 1;
	while(k) {
		if(k & 1) ans = qmul(ans, a);
		a = qmul(a, a);
		k >>= 1;
	}
	return ans;
}

int main() {
	long long n;
	Matrix a, b;
	scanf("%lld", &n);
	a.fib[0][0] = a.fib[0][1] = a.fib[1][0] = 1;
	b = qpow(a, n);
	printf("%lld\n", b.fib[0][1]);
	return 0;
}

更新日志

2025/10/12 07:02

查看所有更新日志

• 7ced7-Reuploads previous blogs于 2025/10/12

版权所有

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)