一、题目描述
二、参考代码
#include <iostream>
#include <vector>using namespace std;const long long MOD = 1e9 + 7;
class Matrix {
public:vector<vector<long long>> data;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;
}
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;
}
