当获得一个递推式时，要求我们求第$N$项，但是这个$N\le 2\times 10^9$很大，单纯的$O(n)$递推无法解决。这个时候就需要用到矩阵乘法来加速递推
矩阵乘法：
设 $A$是$n\ast m$ 矩阵，$B$是$m\ast p$矩阵，则$C=A\ast B$是$n\ast p$矩阵，并且$$\begin{gathered} \forall i\in [1,n],\forall j\in [1,p]: \\ {C}_{i,j}=\sum _{k=1}^m{A}_{i,k}\ast B_{k,j} \end{gathered}$$

斐波那契

题目链接

题意：

求斐波那契数列的第$N$项，$N\le 2\times 10^9$

Sol：

考虑矩阵加速
构造矩阵$①$：
$$\left(\begin{array}{ccc}{a}_n& a_{n-1}& a_{n-2}\end{array}\right)$$
我们要得到矩阵$②$：
$$\left(\begin{array}{ccc}{a}_n+1& a_n& a_{n-1}\end{array}\right)$$
发现需要构造一个$3\times 3$的矩阵，根据矩阵乘法，假设这个矩阵为$③$：
$$\left(\begin{array}{ccc}a& d& g\\ b& e& h\\ c& f& i\end{array}\right)$$
$①\times ③$有：
$$\left(\begin{array}{ccc}a\ast a_n+b\ast a_{n-1}+c\ast a_{n-2}& d\ast a_n+e\ast a_{n-1}+f\ast a_{n-2}& g\ast a_n+h\ast a_{n-1}+i\ast a_{n-2}\end{array}\right)$$
在根据递推式：$a_n=a_{n-1}+a_{n-2},a_0=0,a_1=a_2=1$
可以得出矩阵$③$为：
$$\left(\begin{array}{ccc}1& 1& 0\\ 1& 0& 1\\ 0& 0& 0\end{array}\right)$$
当我们要求第$N$项时，只需求出下式，然后得到的矩阵第一行第一列就是结果：$$\begin{gathered} n\ge 3 \\ \left(\begin{array}{ccc}{a}_2& a_1& a_0\end{array}\right)\ast {\left(\begin{array}{ccc}1& 1& 0\\ 1& 0& 1\\ 0& 0& 0\end{array}\right)}^{n-2} \end{gathered}$$

Code：

#include <bits/stdc++.h>
using namespace std;
const int mod = 10000;
struct matrix{int a[5][5];
}ans, base;matrix mul1(matrix A, matrix B)
{matrix C;for(int i = 0; i < 5; ++i)for(int j = 0; j < 5; ++j)C.a[i][j] = 0;for(int i = 1; i <= 1; ++i)for(int j = 1; j <= 3; ++j){for(int k = 1; k <= 3; ++k){C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j] % mod) % mod;C.a[i][j] %= mod;}}return C;
}
matrix mul2(matrix A, matrix B)
{matrix C;for(int i = 0; i < 5; ++i)for(int j = 0; j < 5; ++j)C.a[i][j] = 0;for(int i = 1; i <= 3; ++i)for(int j = 1; j <= 3; ++j){for(int k = 1; k <= 3; ++k){C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j] % mod) % mod;C.a[i][j] %= mod;}}return C;
}matrix qpow(int b)
{matrix res = ans, a = base;while(b){if(b & 1) res = mul1(res, a);a = mul2(a, a);b >>= 1;}return res;
}int main()
{int n;while(cin >> n && n != -1){if(n == 0) cout << 0 << endl;else if(n <= 2) cout << 1 << endl;else {ans.a[1][1] = 1, ans.a[1][2] = 1, ans.a[1][3] = 0;base.a[1][1] = 1, base.a[1][2] = 1, base.a[1][3] = 0;base.a[2][1] = 1, base.a[2][2] = 0, base.a[2][3] = 0;base.a[3][1] = base.a[3][2] = base.a[3][3] = 0;ans = qpow(n - 2);cout << ans.a[1][1] << endl;}}
}