矩阵加速递推

首先矩阵快速幂模板

struct matrix {
    static constexpr int mod = 1e9 + 7;
    int x, y;
    vector<vector<int>> v;

    matrix() {}

    matrix(int x, int y) : x(x), y(y) {
        v = vector<vector<int>>(x + 1, vector<int>(y + 1, 0));
    }

    void I() {// 单位化
        y = x;
        v = vector<vector<int>>(x + 1, vector<int>(x + 1, 0));
        for (int i = 1; i <= x; i++) v[i][i] = 1;
        return;
    }

    void display() { // 打印
        for (int i = 1; i <= x; i++)
            for (int j = 1; j <= y; j++)
                cout << v[i][j] << " \n"[j == y];
        return;
    }

    friend matrix operator*(const matrix &a, const matrix &b) { //乘法
        assert(a.y == b.x);
        matrix ans(a.x, b.y);
        for (int i = 1; i <= a.x; i++)
            for (int j = 1; j <= b.y; j++)
                for (int k = 1; k <= a.y; k++)
                    ans.v[i][j] = (ans.v[i][j] + a.v[i][k] * b.v[k][j]) % mod;
        return ans;
    }

    friend matrix operator^( matrix x , int y ){ // 快速幂
        assert( x.x == x.y );
        matrix ans(x.x , x.y);
        ans.I();//注意一定要先单位化
        while( y ){
            if( y&1 ) ans = ans*x;
            x = x * x , y >>= 1;
        }
        return ans;
    }
};

例题Luogo P1939

已知数列\(a\)，满足

求数列第\(n\)项对\(10^9+7\)取模

设计状态阵\(mat_i=\begin{bmatrix} a_i \\ a_{i-1}\\ a_{i-2} \end{bmatrix}\)，则\(mat_{i+1}=\begin{bmatrix}a_{i+1}\\a_{i}\\a_{i-1}\end{bmatrix}=\begin{bmatrix}a_{i}+a_{i-2}\\a_{i}\\a_{i-1}\end{bmatrix}\)

可以用待定系数法，加对应项相等解出转移矩阵\(\begin{bmatrix}1&0&1\\1&0&0\\0&1&0\end{bmatrix}\)

则\(mat_{3+n}=\begin{bmatrix}1&0&1\\1&0&0\\0&1&0\end{bmatrix}^n\times mat_3\)