发布时间：2024-07-31

求斐波那契数列

$\left( \begin{matrix} 1 & 1\\ 1 & 0 \end{matrix} \right) \cdot \left( \begin{matrix} f_{i-1}\\ f_{i-2} \end{matrix} \right)= \left( \begin{matrix} f_{i}\\ f_{i-1} \end{matrix} \right)$

模板

struct Matrix{
    // int m[105][105];
    vector<vector<int>> m;
    int x,y;
    Matrix(int _x=0,int _y=0):x(_x),y(_y){m.assign(_x+1,vector<int>(_y+1,-INF));}
    Matrix operator*(const Matrix &t)const{
        Matrix res(x,t.y);
        for(int i=1;i<=x;i++){
            for(int j=1;j<=t.y;j++){
                for(int k=1;k<=y;k++){
                    res.m[i][j]+=m[i][k]*t.m[k][j];
                }
            }
        }
        return res;
    };
};
Matrix qpow(Matrix a,int b){
    Matrix res(a.x,a.y);
    for(int i=1;i<=a.x;i++)res.m[i][i]=1;
    while(b){
        if(b&1)res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
void solve(){
    int n,k;
    cin>>n>>k;
    Matrix a;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cin>>a.a[i][j];
    }
    a=qpow(a,k);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cout<<a.a[i][j]<<" \n"[j==n];
    }
}