---

一、題目描述

---

二、參考代碼

#include <iostream>
#include <vector>using namespace std;const long long MOD = 1e9 + 7; // 取模的值// 定義矩陣類
class Matrix {
public:vector<vector<long long>> data;// 構造函數，創建一個大小為 size x size 的矩陣，初始化為0Matrix(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;
}

---