---

一、前置知識：向量（一列或一行的矩陣）、矩陣

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°B=C$。

矩陣點乘的符號為“$°$”，其中$A$、$B$、$C$均為矩陣，且維度相同。運算方法也很簡單，$C_{i,j}=A_{i,j}\times B_{i,j}$。

（2）定義：向量點乘

我們再設$A?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行}?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}$，即方向相反。

四、結尾