【题目来源】
洛谷：P1962 斐波那契数列 - 洛谷
【题目描述】
大家都知道，斐波那契数列是满足如下性质的一个数列：
\[F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.
\]
请你求出 \(F_n \bmod 10^9 + 7\) 的值。
【输入】
一行一个正整数 \(n\)。
【输出】
输出一行一个整数表示答案。
【输入样例】
5
【输出样例】
5
【解题思路】
【算法标签】
《洛谷 P1962 斐波那契数列》 #数学# #递推# #矩阵运算# #矩阵乘法#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
int n, ans;// 定义矩阵结构体
struct Mat
{int num[5][5]; // 矩阵元素，5x5大小但实际只用到2x2
}A, B; // A: 转移矩阵，B: 结果矩阵// 矩阵乘法函数
Mat mul(Mat x, Mat y)
{Mat res = {}; // 初始化结果矩阵为0for (int i=1; i<=2; i++){for (int j=1; j<=2; j++){for (int k=1; k<=2; k++){res.num[i][j] += x.num[i][k] * y.num[k][j]; // 矩阵乘法res.num[i][j] %= mod; // 取模防止溢出}}}return res; // 返回结果矩阵
}// 矩阵快速幂
Mat quick(Mat x, int y)
{Mat res = {}; // 初始化结果矩阵res.num[1][1] = res.num[2][2] = 1; // 初始化为单位矩阵Mat base = x; // 基础矩阵while (y) // 快速幂计算{if (y%2) // 如果指数是奇数{res = mul(res, base); // 乘以当前base}base = mul(base, base); // base自乘y /= 2; // 指数减半}return res; // 返回结果矩阵
}signed main() // 因为使用#define int long long，所以用signed main
{cin >> n; // 输入nif (n<=2) // 前两项特殊情况{cout << 1 << endl; // 前两项都是1return 0;}// 初始化转移矩阵A// 对于斐波那契数列的转移矩阵是：// [F(n) F(n-1)] = [F(n-1) F(n-2)] * [1 1]// [1 0]A.num[1][1] = 1; // 第一行第一列A.num[1][2] = 1; // 第一行第二列A.num[2][1] = 1; // 第二行第一列A.num[2][2] = 0; // 第二行第二列（默认是0）B = quick(A, n-2); // 计算A的(n-2)次幂，得到转移矩阵// 计算第n项斐波那契数// 根据公式：[F(n) F(n-1)] = [F(2) F(1)] * A^(n-2)// 其中F(1)=1, F(2)=1ans = (B.num[1][1] + B.num[2][1]) % mod; // 计算F(n)cout << ans << endl; // 输出结果return 0;
}
【运行结果】
5
5