首先定义斐波那契数列问题：
定义 a_0=1a0=1, a_1=1a1=1, a_n=a_{n−1}+a_{n−2}an=an−1+an−2，求 a_nan 是多少。
为了避免考虑整数溢出问题，我们求 a_n%pan 的值，p=10^9+7p=109+7 。
递归计算的节点个数是 O(2^n)O(2n) 的级别的，存在大量重复计算。
时间复杂度是 O(2^n)O(2n) ，一秒内大约能算到第三四十项。
C++ 代码
const int MOD = 1000000007;
int f(int n)
{
if (n <= 1) return 1;
return (f(n - 1) + f(n - 2)) % MOD;
}
Copy
算法2——记忆化搜索开一个大数组记录中间结果，如果一个状态被计算过，则直接查表，否则再递归计算。
总共有 nn 个状态，计算每个状态的复杂度是 O(1)O(1) ，所以时间复杂度是 O(n)O(n) 。
一秒内算 n=10^7n=107 毫无压力，但由于是递归计算，递归层数太多会爆栈，大约只能算到 n=10^5n=105 级别。
C++ 代码
const int N = 100000, MOD = 1000000007;
int a[N];
int f2(int n)
{
if (a[n]) return a[n];
if (n <= 1) return 1;
a[n] = f2(n - 1) + f2(n - 2);
a[n] %= MOD;
return a[n];
}
Copy
算法3——递推开一个大数组，记录每个数的值。用循环递推计算。
总共计算 nn 个状态，所以时间复杂度是 O(n)O(n) 。
但需要开一个长度是 nn 的数组，内存将成为瓶颈，当 n=10^8n=108 时，需要的内存是 4∗1081024×1024≈381MB4∗1081024×1024≈381MB。
式子中乘 4 是因为 C++ 中 int 类型占 4 字节。
C++代码
const int N = 100000000, MOD = 1000000007;
int f3(int n)
{
a[0] = a[1] = 1;
for (int i = 2; i <= n; i ++ )
{
a[i] = a[i - 1] + a[i - 2];
a[i] %= MOD;
}
return a[n];
}
Copy
算法4——递推+滚动变量仔细观察我们会发现，递推时我们只需要记录前两项的值即可，没有必要记录所有值，所以我们可以用滚动变量递推。
时间复杂度还是 O(n)O(n)，但空间复杂度变成了 O(1)O(1) 。
C++代码：
const int MOD = 1000000007;
int f4(int n)
{
int x, y, z;
x = y = 1;
for (int i = 2; i <= n; i ++ )
{
z = (x + y) % MOD;
x = y;
y = z;
}
return z;
}
Copy
算法5——矩阵运算 + 快速幂。用算法 4 我们 1 秒内最多可以算到 10^8108 级别，那当 nn 更大时该怎么办呢？
可以先利用矩阵运算的性质将通项公式变成幂次形式，然后用平方倍增（快速幂）的方法求解第 nn 项。
首先我们定义向量
X_n=[a_n a_{n−1}] ,边界：X_1=[a_1 a_0]Xn=[an an−1],边界：X1=[a1 a0]
然后我们可以找出矩阵：
begin{bmatrix} 1 & 1 \ 1 & 0 end{bmatrix}[1110]
则有：
X_n=X_{n−1}×AXn=Xn−1×A
所以：
X_n=X_1×A^{n−1}Xn=X1×An−1
由于矩阵具有结合律，所以我们可以先求出 A^{n−1}%PAn−1 ，然后再用 X_1X1 左乘，即可求出 X_nXn ，向量 X_nXn 的第一个元素就是 a_nan。
时间复杂度分析：快速幂的时间复杂度是 O(log n)O(logn) ，所以算法 5 的时间复杂度也是 O(log n)O(logn) 。
C++代码
#include#include #include #include #include using namespace std; const int MOD = 1000000007; // 矩阵运算 计算 c = a × b void mul(int a[][2], int b[][2], int c[][2]) { int temp[][2] = {{0, 0}, {0, 0}}; for (int i = 0; i < 2; i ++ ) for (int j = 0; j < 2; j ++ ) for (int k = 0; k < 2; k ++ ) { long long x = temp[i][j] + (long long)a[i][k] * b[k][j]; temp[i][j] = x % MOD; } for (int i = 0; i < 2; i ++ ) for (int j = 0; j < 2; j ++ ) c[i][j] = temp[i][j]; } int f_final(long long n) { int x[2] = {1, 1}; // X_1 矩阵 int res[][2] = {{1, 0}, {0 , 1}}; // 单位矩阵，用来保存 A int t[][2] = {{1, 1}, {1, 0}}; // // 快速幂运算，计算 A^(n-1) long long k = n - 1; while (k) { if (k&1) mul(res, t, res); mul(t, t, t); k >>= 1; } // 计算 X_1 * A^(n-1) int c[2] = {0, 0}; // X_n for (int i = 0; i < 2; i ++ ) for (int j = 0; j < 2; j ++ ) { long long r = c[i] + (long long)x[j] * res[j][i]; c[i] = r % MOD; } return c[0]; } int main() { long long n ; cin >> n; cout << f_final(n) << endl; return 0; }
Copy
附：快速幂运算模板求 m^k%pmk%p 时间复杂度 O(log k)O(logk)
代码：
// 利用二分(倍增)的思想 在 k 为偶数时，将 m^k 拆解为 （m^2）^(k/2)，来极大减少运算量
int pw(int m, int k, int p)
{
int res = 1 % p, t = m;
while (k)
{
if (k&1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
Copy
通项公式法此法 O(1)O(1) 时间，应用此法的前提是知道斐波那契数列的通项公式：
F_n = frac{(frac{1+sqrt{5}}{2})^n-(frac{1-sqrt{5}}{2})^n}{sqrt{5}}Fn=5(21+5)n−(21−5)n
将 nn 代入计算即可，代码略，需要注意浮点数的算术运算有精度损失，因此，结果在 nn 较大时可能会有错误。
