矩阵加速
快速斐波那契数列
[[快速幂#矩阵快速幂|矩阵快速幂]]是求解斐波那契数列的一个高效方法，特别是当需要计算的斐波那契数非常大时。斐波那契数列定义如下：
其中，，。
斐波那契数列与矩阵乘法
斐波那契数列可以通过矩阵乘法来表示。考虑以下矩阵：
将这个矩阵称为矩阵 。现在，如果我们计算 的 次幂，并将结果与矩阵 相乘，我们将得到一个包含 和 的矩阵：
这意味着通过计算矩阵 的 次幂，我们可以直接得到斐波那契数列中的第 项。
如何使用[[快速幂#矩阵快速幂|矩阵快速幂]]计算
矩阵快速幂算法允许我们高效地计算矩阵 的幂。基本思想是利用幂的性质： 和 。这意味着我们可以通过递归地平方矩阵来减少乘法的次数，从而以对数时间复杂度计算矩阵的幂。这种方法比直接计算每个斐波那契数要高效得多，特别是对于大数。
示例代码
以下是一个简单的示例，展示了如何使用矩阵快速幂来计算斐波那契数列的第 项：
CPP
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <iostream>
#include <vector>
using namespace std;
typedef vector<vector<int>> Matrix;
Matrix multiplyMatrix(const Matrix& a, const Matrix& b) {
int n = a.size();
Matrix result(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
result[i][j] += a[i][k] * b[k][j];
}
}
}
return result;
}
Matrix quickPow(Matrix a, int power) {
int n = a.size();
Matrix result(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) {
result[i][i] = 1;
}
while (power > 0) {
if (power & 1) {
result = multiplyMatrix(result, a);
}
a = multiplyMatrix(a, a);
power >>= 1;
}
return result;
}
int fibonacci(int n) {
if (n <= 1) {
return n;
}
Matrix mat = {{1, 1}, {1, 0}};
Matrix result = quickPow(mat, n - 1);
return result[0][0];
}
int main() {
int n = 10; // 计算第10个斐波那契数
cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
return 0;
}
这段代码定义了如何使用矩阵快速幂来计算斐波那契数列的第 项。通过计算矩阵 的 次幂，我们可以直接得到 。这种方法的时间复杂度是 ，远远优于直接递归计算的 或线性迭代的 。
例题：1213. 斐波那契 - AcWing题库提示： 所以有
得到