输入 n，求斐波那契数列第 n 项模 9 9 9 7 9997 的值。 斐波那契数列的第一项值为 1 1 ，第二项值为 2 2 。c++

可以使用矩阵快速幂求解斐波那契数列的第 n 项，时间复杂度为 O(logn)。具体实现如下：

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 9997999; // 这里是 9997 * 1000 + 999
typedef vector<vector<int>> Matrix;

// 矩阵乘法
Matrix mul(const Matrix& A, const Matrix& B) {
    int n = A.size(), m = B[0].size(), t = A[0].size();
    Matrix C(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < t; k++) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
            }
        }
    }
    return C;
}

// 矩阵快速幂
Matrix pow(const Matrix& A, int n) {
    if (n == 1) return A;
    Matrix T = pow(A, n / 2);
    T = mul(T, T);
    if (n % 2 == 1) T = mul(T, A);
    return T;
}

int fib(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    Matrix A(2, vector<int>(2));
    A[0][0] = A[0][1] = A[1][0] = 1;
    Matrix B = pow(A, n - 2);
    return (2 * B[0][0] + B[0][1]) % MOD;
}

int main() {
    int n;
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}

需要注意的是，这里的模数不是 9997，而是 9997999，因为 9997 不是质数。另外，由于斐波那契数列的第一项和第二项不是 1 和 1，所以需要特判一下。