一、题目描述

二、参考代码

#include <iostream>
#include <vector>

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;
}