发布时间：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 a[N][N];
    Matrix(){
        memset(a,0,sizeof a);
    }
    Matrix operator * (const Matrix &b)const{
        Matrix res;
        for(int i=1;i<N;i++){
            for(int j=1;j<N;j++){
                for(int k=1;k<N;k++)(res.a[i][j]+=a[i][k]*b.a[k][j])%=mod;
            }
        }
        return res;
    }
};
Matrix qpow(Matrix a,int b){
    Matrix ans;
    for(int i=1;i<N;i++)ans.a[i][i]=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a;
        a=a*a;
    }
    return ans;
}
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];
    }
}