---

一、前置知识：向量（一列或一行的矩阵）、矩阵

1. 行向量

例如$\left[\begin{array}{ccc}1& 1& 4\end{array}\right]$，这就是一个行向量，$\left[\begin{array}{ccc}1& 1& 4\end{array}\right]$可以理解为一个$1$行$3$列矩阵。

行向量：$\left[\begin{array}{ccc}{a}_1& \dots & a_n\end{array}\right]$，$n$为任意取值。

2. 列向量

例如$\left[\begin{array}{c}5\\ 1\\ 4\end{array}\right]$，这就是一个列向量，$\left[\begin{array}{c}5\\ 1\\ 4\end{array}\right]$可以理解为一个$3$行$1$列的矩阵。

列向量：$\left[\begin{array}{c}{a}_1\\ ⋮\\ a_n\end{array}\right]$，$n$为任意取值。

3. 向量其余基本概念

向量是一个有方向与大小的量，它的起点可以是任意位置。

维度：
$\left[\begin{array}{c}{a}_1\end{array}\right]$，这是一个一维向量，它仅有一个数字。而$\left[\begin{array}{c}{a}_1\\ ⋮\\ a_n\end{array}\right]$与$\left[\begin{array}{ccc}{a}_1& \dots & a_n\end{array}\right]$，它们都是$n$维的。

长度：
向量的长度也就是它的大小，我们称它为模。而模则为向量起点与终点之间的距离。

4. 矩阵基本概念

$\left[\begin{array}{ccc}1& 1& 4\\ 1& 6& 1\\ 4& 1& 5\end{array}\right]$注： 这是一个维度为$3\times 3$的矩阵。

一个矩阵的维度表示为$m\times n$，即$m$行$n$列的矩阵。

5. 关于它们的细节

向量可以视为一种特殊的矩阵，我们通常用大写字母表示矩阵；小写字母表示向量，可带一个小箭头，例如$\vec{v}$。例如$v_i$表示向量$v$的第$i$项（即第$i$个元素，行向量从左往右数，列向量从上往下），$a_{i,j}$或$A_{i,j}$表示矩阵$A$的第$i$行第$j$列的元素。

二、运算

下文由于向量可以视为一种特殊的矩阵，且为了方便所以均用大写字母表示向量或矩阵。

1. 转置

（1）定义

$A^T$表示对$A$进行转置，即$A$的第$i$行将变成
$A^T$的第$i$列。若$A=\left[\begin{array}{ccc}1& 1& 4\\ 5& 1& 4\end{array}\right]$，则$A^T=\left[\begin{array}{cc}1& 5\\ 1& 1\\ 4& 4\end{array}\right]$。

（2）性质

• $(A^T{)}^T=A$
• $(A+B{)}^T=A^T+B^T$

2. 矩阵（向量）与矩阵（向量）的加减法

我们设$A\pm B=C$。

$A\pm B$不是随便的，$A$与$B$要求维度相同。且$C$维度仍与$A$、$B$相同。
运算方式，$C_{i,j}=A_{i,j}\pm B_{i,j}$。

3. 点乘与乘法

（1）定义：矩阵点乘

我们设$A\circ B=C$。

矩阵点乘的符号为“$\circ$”，其中$A$、$B$、$C$均为矩阵，且维度相同。运算方法也很简单，$C_{i,j}=A_{i,j}\times B_{i,j}$。

（2）定义：向量点乘

我们再设$A\cdot B=n$。

显然$A$、$B$均为向量，且维度相同，而$n$又是一个标量。那$n$为多少？$n={\sum }_{i=1}^m{A}_{i,j}{B}_{i,j}$（$m$为$A$、$B$的维度）。

（3）定义：矩阵（向量）与标量的乘法

我们再设$nA=B$。

则$A$、$B$为矩阵（向量），$n$为标量，显而易见$B_{i,j}=n{A}_{i,j}$。

（4）定义：矩阵（向量）与矩阵（向量）的乘法

我们再再设$AB=C$，设$A$维度为$m\times n$，而$B$维度为$n\times p$，则$C$维度为$m\times p$。

运算方式大概如此（复杂）：$C_{i,j}=A_{i行}\cdot B_{j列}$，即$C_{i,j}={\sum }_{i=1}^n{A}_{i,k}{B}_{k,j}$。

（5）性质：矩阵（向量）与矩阵（向量）的乘法

• 没有交换律。
• 有结合律和分配率。

（6）应用：矩阵快速幂，进行加速

现在目光转置P1962，要运用矩阵乘法来解决求斐波那契数列第$n$项（对$10^9+7$取模）。

我们构造一个矩阵$A$与矩阵$B$，$A=\left[\begin{array}{cc}x& y\end{array}\right]$，$B=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$，而$AB=\left[\begin{array}{cc}x+y& x\end{array}\right]$。现在设$x$是斐波那契数列的第$(i+1)$项（简记$F_{i+1}$），$y$则为第$i$项（简记$F_i$）。再把目光转回矩阵，$A=\left[\begin{array}{cc}{F}_{i+1}& F_i\end{array}\right]$，
则$AB=\left[\begin{array}{cc}{F}_{i+1}+F_n& F_{i+1}\end{array}\right]$，根据斐波那契数列的规律，$F_{i+1}+F_i=F_{i+2}$，so $AB=\left[\begin{array}{cc}{F}_{i+2}& F_{i+1}\end{array}\right]$，很容易发现$AB$比$A$中每项都进了一位，也就是说只要一直乘$B$直至结果矩阵为$\left[\begin{array}{cc}{F}_n& F_{n-1}\end{array}\right]$，第一项就是P1962的答案。

但是直接递推到$F_n$是$O(n)$的，乘到$F_n$也是$O(n)$的。但是多个相同数相乘是数的幂，多个相同矩阵相乘是矩阵的幂，同样也可以使用快速幂，现在复杂度大约为$O(klo{g}_{2}n)$（有些小细节没有提及），$k$为矩阵乘法运算时耗掉的。这时当$n$的值到达一个程度，时间就会大幅减少。

代码如下。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll p=1e9+7;
struct mat{
	ll nr,nc;
	ll m[15][15];
	mat(ll NR=0,ll NC=0){
		nr=NR,nc=NC;
		memset(m,0,sizeof(m));
	}
	mat operator=(mat b){
		nr=b.nr;
		nc=b.nc;
		for(int i=1;i<=nr;i++)
			for(int j=1;j<=nc;j++)
				m[i][j]=b.m[i][j];
	}
};
mat operator*(mat a,mat b){
	mat c(a.nr,b.nc);
	for(int i=1;i<=a.nr;i++){
		for(int j=1;j<=b.nc;j++){
			for(int k=1;k<=a.nc;k++){
				c.m[i][j]=(a.m[i][k]*b.m[k][j]%p+c.m[i][j])%p;
			}
		}
	}
	return c;
}
mat fastpow(mat a,ll b){
	if(b==1)return a;
	if(b%2==0)return fastpow(a*a,b/2);
	else return fastpow(a*a,b/2)*a;
}
int main(){
	ll n;
	cin>>n;
	if(n<=2){
		cout<<1;
		return 0;
	}
	mat fib(1,2),tmp(2,2),tmp2;
	fib.m[1][1]=1,fib.m[1][2]=1;
	tmp.m[1][1]=1,tmp.m[1][2]=1;
	tmp.m[2][1]=1;
	tmp2=fib*fastpow(tmp,n-2);
	cout<<tmp2.m[1][1];
}

三、拓展

1. 向量表示里的几何意义

例如有一个二维向量，$\vec{v}=\left[\begin{array}{c}x\\ y\end{array}\right]$，它将原点$(0,0)$作为起点时，它的终点就是$(x,y)$。

2. 向量加法里的几何意义

如图，向量$a$与向量$b$头尾相接最终与向量$c$到达同一目的地，而恰好$\vec{a}+\vec{b}=\vec{c}$。

3. 向量求反里的几何意义

$\vec{a}$与$-\vec{a}$的区别在于将$\vec{a}$旋转$180°$就可以得$-\vec{a}$，即方向相反。

四、结尾