P1962 斐波那契数列
题目地址：P1962 斐波那契数列 – 洛谷 | 计算机科学教育新生态
前置知识点
矩阵
定义：
一个$n\times m$矩阵是由$n\times m$个实数排列成$n$行$m$列构成的，用一对[]括起来。
下面$3\times 3$矩阵简记为$A=(a_{ij})_{3\times 3}$
A=\left[
\begin{matrix}
a_{11} & a_{12} & a_{13}\\
a_{21} & a_{22} & a_{23}\\
a_{31} & a_{32} & a_{33}\\
\end{matrix}
\right]
$$
矩阵加减
$n$行$m$列矩阵$A,B$加减规则：$A\pm B=(a_{ij}\pm b_{ij})_{n\times m}$
矩阵加减满足交换律，结合律
\begin{aligned} A\pm B&=
\left[\begin{matrix}
a_{11}&a_{12}&\cdots&a_{1m}\\
a_{21}&a_{22}&\cdots&a_{2m}\\
\cdots&\cdots&\cdots&\cdots\\
a_{n1}&a_{n2}&\cdots&a_{nm}\\
\end{matrix}\right]\pm
\left[\begin{matrix}
b_{11}&b_{12}&\cdots&b_{1m}\\
b_{21}&b_{22}&\cdots&b_{2m}\\
\cdots&\cdots&\cdots&\cdots\\
b_{n1}&b_{n2}&\cdots&b_{nm}\\
\end{matrix}\right]\\&=
\left[\begin{matrix}
a_{11}\pm b_{11}&a_{12}\pm b_{12}&\cdots&a_{1m}\pm b_{1m}\\
a_{21}\pm b_{21}&a_{22}\pm b_{22}&\cdots&a_{2m}\pm b_{2m}\\
\cdots&\cdots&\cdots&\cdots\\
a_{n1}\pm b_{n1}&a_{n2}\pm b_{n2}&\cdots&a_{nm}\pm b_{nm}\\
\end{matrix}\right]
\end{aligned}
$$
矩阵乘法
1.数和矩阵相乘
kA=Ak=
\left[\begin{matrix}
ka_{11}&ka_{12}&\cdots&ka{1m}\\
ka_{21}&ka_{22}&\cdots&ka{2m}\\
\cdots&\cdots&\cdots&\cdots\\
ka_{n1}&ka_{n2}&\cdots&ka{nm}\\
\end{matrix}\right]
$$
2.矩阵和矩阵相乘
原理：$C_{ij}=A$的第$i$行和$B$的第$j$列每个元素对应相乘的和。
所以矩阵乘法当且仅当A的列数=B的行数时才有定义。
由于矩阵乘法的规则，$A\cdot B\not= B\cdot A$
具体方法：$\textcolor{red}{C_{ij}}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots+a_{it}b_{tj}=\textcolor{red}{\sum_{r=1}^{t}a_{ir}b_{rj}}$
实现
struct matrix {
int n, m;
int a[100][100];
};
// A.m == B.n
matrix matrix_mul(matrix A, matrix B) {
matrix C;
C.n = A.n;
C.m = B.m;
for (int i = 0; i < A.n; ++i) {
for (int j = 0; j < B.m; ++j) {
C.a[i][j] = 0;
for (int k = 0; k < A.m; ++k) {
C.a[i][j] += A.a[i][k] * B.a[k][j];
}
}
}
return C;
}
单位矩阵
形如：
\left[\begin{matrix}
1&0&\cdots&0\\
0&1&\cdots&0\\
\cdots&\cdots&\cdots&\cdots\\
0&0&0&1\\
\end{matrix}\right]
$$
主对角线上元素均为1，其余元素均为0的矩阵。通常记做$I_n$或$E_n$
性质：
$A\cdot I_n=A$
$I_n\cdot A=A$
即任何一个矩阵左乘或右乘单位矩阵，结果不变（相当于乘法当中的 $1$ ）
矩阵快速幂
快速幂
int quick_power(int x,int y){
int ans = 1,cnt = x;
while(y){
if(y & 1){
ans *= cnt;
}
cnt *= cnt;
y >>= 1;
}
return ans;
}
矩阵快速幂
利用快速幂思想，快速求矩阵$A^n$
将快速幂中的乘法替换为矩阵乘法，参数和返回值替换为矩阵即可。
int n; // 所有矩阵都是 n * n 的矩阵
struct matrix {
int a[100][100];
};
matrix matrix_mul(matrix A, matrix B, int mod) {
// 2 个矩阵相乘
matrix C;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
C.a[i][j] = 0;
for (int k = 0; k < n; ++k) {
C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j] % mod) % mod;
}
}
}
return C;
}
matrix unit() {
// 返回一个单位矩阵
matrix res;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
res.a[i][j] = 1;
} else {
res.a[i][j] = 0;
}
}
}
return res;
}
matrix matrix_pow(matrix A, int p, int mod) {
// 快速求矩阵 A 的 p 次方
matrix res = unit();
while (p > 0) {
if (p & 1) {
res = matrix_mul(res, A, mod);
}
A = matrix_mul(A, A, mod);
p >>= 1;
}
return res;
}
本题题解
斐波那契数列递推式：
a_n=a_{n-1}+a_{n-2}
$$
设$A_i=\left[\begin{matrix}a_i,a_{i+1}\end{matrix}\right]$
先构造$1\times 2$的矩阵$A_1=\left[\begin{matrix}a_1,a_2\end{matrix}\right]$，考虑构造矩阵 $B$ 使得 $A_1\times B=A_2$
通过观察推导得到$B=\left[\begin{matrix}0&1\\1&1\end{matrix}\right]$
\begin{aligned}
&\therefore A_2=A_1\times B\\
&\therefore A_3=A_2\times B=A_1\times B\times B=A_1\times B^2
\end{aligned}
$$
\cdots
$$
A_i=A_1\times B^{i-1}=
\left[\begin{matrix}1,1\end{matrix}\right]
\times
\left[\begin{matrix}
0&1\\
1&1\\
\end{matrix}\right]^{i-1}
$$
时间复杂度：$\mathcal{O}(\log N)$