【提高】斐波那契数列_矩阵加速
题目描述
大家都知道，斐波那契数列是满足如下性质的一个数列：
$$F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.$$请你求出 的值。
- 虽然原理讲了很多，但代码写起来很简单！！
（点击展开）大家可以参考下面的矩阵快速幂模板
#include <bits/stdc++.h>
using namespace std;
/*--------------------------------- 矩阵快速幂 begin------------------------------------------------*/
// 来自: https://www.luogu.com.cn/article/87ooh5ay
using i64 = long long;
const int P = 1000000007;
template<typename T>
struct Matrix {
int n;
vector<vector<T>> mat;
// n_ 是矩阵大小, x 是对角线初值
Matrix(int n_, T x) {
n = n_;
mat.assign(n, vector<T>(n, 0));
for (int i = 0; i < n; i++) mat[i][i] = x;
}
// 重载 Matrix 的 *
Matrix operator*(const Matrix& b) {
Matrix ans(n, 0);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
ans.mat[i][j] = (ans.mat[i][j] + (i64) mat[i][k] * b.mat[k][j]) % P;
}
}
return ans;
}
};
// n >= 1, 二进制求快速幂
template<typename T>
T power(T x, i64 n) {
T ans = x; n -= 1;
for (; n > 0; n >>= 1, x = x * x) if (n & 1) ans = ans * x;
return ans;
}
/*--------------------------------- 矩阵快速幂 end --------------------------------------------------*/
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 n;
cin >> n;
if (n <= 2) cout << 1 << '\n';
else {
// [f2, f3] = [f1, f2] * a
Matrix<int> a(2, 0);
a.mat = {
{0, 1},
{1, 1}
};
a = power(a, n - 2);
// [fn-1, fn] = [1, 1] * a
i64 fn = (a.mat[0][1] + a.mat[1][1]) % P;
cout << fn << '\n';
}
return 0;
}
输入格式
一行一个正整数
输出格式
输出一行一个整数表示答案。
5
5
10
55
123456789
62791945
提示
【样例 #1 解释】