题解 | 斐波那契数列

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const long long MOD = 1000000007;

// 2x2矩阵结构体（带模运算）
struct Matrix {
    long long a, b, c, d;
    Matrix(long long a = 1, long long b = 1, long long c = 1, long long d = 0) 
        : a(a % MOD), b(b % MOD), c(c % MOD), d(d % MOD) {}
};

// 带模运算的矩阵乘法
Matrix multiplyMod(const Matrix& m1, const Matrix& m2, long long mod) {
    return Matrix(
        (m1.a * m2.a + m1.b * m2.c) % mod,
        (m1.a * m2.b + m1.b * m2.d) % mod,
        (m1.c * m2.a + m1.d * m2.c) % mod,
        (m1.c * m2.b + m1.d * m2.d) % mod
    );
}

// 矩阵快速幂（带模运算）
Matrix matrixPowerMod(Matrix base, long long n, long long mod) {
    Matrix result(1, 0, 0, 1); // 单位矩阵
    
    while (n > 0) {
        if (n & 1) {
            result = multiplyMod(result, base, mod);
        }
        base = multiplyMod(base, base, mod);
        n >>= 1;
    }
    return result;
}

// 求斐波那契数（模运算）
long long fibonacciMod(long long n, long long mod = MOD) {
    if (n <= 1) return n % mod;
    
    Matrix base(1, 1, 1, 0);
    Matrix result = matrixPowerMod(base, n - 1, mod);
    return result.a % mod;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int k;
    cin >> k;
    cout << fibonacciMod(k) << endl;
    
    return 0;
}

什么你有通项公式？什么你的通项公式有无理数？

跟我的矩阵快速幂说去吧！复杂度O(logn)，调用函数的开销可比计算还大了