文章目录

• 一、题目描述
• 二、参考代码

一、题目描述

二、参考代码

#include 
#include 
using namespace std;
const long long MOD = 1e9 + 7; // 取模的值
// 定义矩阵类
class Matrix {
public:
vector<vector<long long>> data;
// 构造函数，创建一个大小为 size x size 的矩阵，初始化为0
Matrix(int size) : data(size, vector<long long>(size, 0)) {}
// 矩阵乘法
Matrix operator*(const Matrix& other) const {
int size = data.size();
Matrix result(size);
for (int i = 0; i < size; ++i) {
for (int j = 0; j < size; ++j) {
for (int k = 0; k < size; ++k) {
result.data[i][j] += (data[i][k] * other.data[k][j]) % MOD;
result.data[i][j] %= MOD; // 取模运算
}
}
}
return result;
}
};
// 计算矩阵快速幂
Matrix matrixPower(Matrix base, int n) {
int size = base.data.size();
Matrix result(size);
// 初始化为单位矩阵
for (int i = 0; i < size; ++i) {
result.data[i][i] = 1;
}
// 循环计算幂
while (n > 0) {
if (n & 1) {
result = result * base;
}
base = base * base;
n >>= 1;
}
return result;
}
// 计算斐波那契数列的第 n 项
long long fibonacci(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
Matrix base(2);
base.data[0][0] = 1;
base.data[0][1] = 1;
base.data[1][0] = 1;
base.data[1][1] = 0;
Matrix result = matrixPower(base, n - 1);
return result.data[0][0] % MOD;
}
int main() {
int n;
while (cin >> n)
{
long long result = fibonacci(n);
cout << result << endl;
}
return 0;
}