给定n，求斐波那契数列第n项对1e9+7取模的值
由于数据太大，朴素的递推会超时，所以我们考虑用矩阵优化。
首先我们要明确矩阵乘法的运算法则，假设A是一个n*m的矩阵，B是一个m*p的矩阵，C是一个n*p的矩阵且满足C=A*B，那么存在
$$C_{i,j}=\sum\limits_{k=1}^{m}{A_{i,k}*B_{k,j}}$$
举一个简单的例子就能直观的反映这个式子：
$$
\left[
\begin{matrix}
2 & 3 \\
4 & 5
\end{matrix}
\right] \times
\left[
\begin{matrix}
6 \\
7
\end{matrix}
\right] =
\left[
\begin{matrix}
2*6+3*7 \\
4*6+5*7
\end{matrix}
\right]
$$
然后我们考虑如何优化斐波那契数列
我们假设$Fib(n)$表示一个矩阵
$
\left[
\begin{matrix}
f_{n} & f_{n-1}
\end{matrix}
\right]
$，那么我们希望有一个矩阵base，使得$Fib(n-1)\times base = Fib(n)$，也就是我们希望这样：
$$
\left[
\begin{matrix}
f_{n - 1} & f_{n - 2}
\end{matrix}
\right] \times base =
\left[
\begin{matrix}
f_{n} & f_{n-1}
\end{matrix}
\right]
$$
那么我们显然可以看出
$base=
\left[
\begin{matrix}
1 & 1 \\
1 & 0
\end{matrix}
\right]
$
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int mod = 1e9 + 7; 4 typedef long long ll; 5 ll n; 6 struct Matrix { 7 ll m[3][3]; 8 Matrix() { 9 memset(m, 0, sizeof(m)); 10 } 11 Matrix operator *(const Matrix &x) const { 12 Matrix ret; 13 for (register int i = 1; i <= 2; ++i) 14 for (register int j = 1; j <= 2; ++j) 15 for (register int k = 1; k <= 2; ++k) 16 ret.m[i][j] = (ret.m[i][j] + m[i][k] * x.m[k][j]) % mod; 17 return ret; 18 } 19 } a, base; 20 void qpow(ll p) { 21 while (p) { 22 if (p & 1) a = a * base; 23 base = base * base; 24 p >>= 1; 25 } 26 } 27 int main() { 28 scanf("%lld", &n); 29 if (n <= 2) { 30 puts("1"); 31 return 0; 32 } 33 base.m[1][1] = base.m[1][2] = base.m[2][1] = 1; 34 a.m[1][1] = a.m[1][2] = 1; 35 qpow(n - 2); 36 printf("%lld\n", a.m[1][1] % mod); 37 return 0; 38 }
原文：https://www.cnblogs.com/shl-blog/p/11335378.html
