#include <bits/甩头dc++.h> using namespace std; int main() { long long n,a[100]; //cin>>n; a[1]=1; a[2]=2; a[3]=4; for(int i=4;i<=50;i++){ a[i] = a[i-1]+a[i-2]+a[i-3]; } while(cin>>n){ cout<<a[n]<<endl; } }请帮我优化这段代码

这段代码的时间复杂度为 O(n)，可以考虑使用矩阵快速幂来优化。

以下是优化后的代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int mod = 1e9 + 9;

struct Matrix {
    LL a[4][4];
    Matrix() {
        memset(a, 0, sizeof(a));
    }
    Matrix operator * (const Matrix &b) const {
        Matrix c;
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= 3; j++) {
                for (int k = 1; k <= 3; k++) {
                    c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % mod) % mod;
                }
            }
        }
        return c;
    }
};

Matrix qpow(Matrix a, LL b) {
    Matrix ans;
    ans.a[1][1] = ans.a[2][2] = ans.a[3][3] = 1;
    while (b) {
        if (b & 1) {
            ans = ans * a;
        }
        a = a * a;
        b >>= 1;
    }
    return ans;
}

int main() {
    LL n;
    while (cin >> n) {
        Matrix a;
        a.a[1][1] = 1; a.a[1][2] = 1; a.a[1][3] = 1;
        a.a[2][1] = 1; a.a[2][2] = 0; a.a[2][3] = 0;
        a.a[3][1] = 0; a.a[3][2] = 1; a.a[3][3] = 0;
        Matrix b = qpow(a, n - 2);
        LL ans = ((b.a[1][1] * 4) % mod + (b.a[1][2] * 2) % mod + b.a[1][3]) % mod;
        cout << ans << endl;
    }
    return 0;
}

时间复杂度降为 O(log n)。