【模板】矩阵快速幂

单位矩阵相当于普通乘法算术中的单位元。

代码如下

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=101;

inline ll read(){
    ll x=0,f=1;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
    do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));
    return f*x;
}

int n;ll m;
ll c[maxn][maxn],ans[maxn][maxn],res[maxn][maxn];

void mul(ll a[][maxn],ll b[][maxn]){
    memset(res,0,sizeof(res));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                res[i][j]=(res[i][j]+a[i][k]*b[k][j]%mod)%mod;
    memcpy(a,res,sizeof(res));
}

void read_and_parse(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)c[i][j]=read();
    for(int i=1;i<=n;i++)ans[i][i]=1;
}
void solve(){
    for(;m;m>>=1,mul(c,c))if(m&1)mul(ans,c);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)printf("%lld ",ans[i][j]);
        puts("");
    }
}
int main(){
    read_and_parse();
    solve();
    return 0;
}

【模板】矩阵快速幂

原文：https://www.cnblogs.com/wzj-xhjbk/p/10617234.html