代码

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

ll mod=0,isMod=0;  //是否取模
struct M{
    int n,m;
    ll g[55][55];
    friend M operator + (M a,M b){
        M c;
        memset(c.g,0,sizeof c.g);
        c.n=a.n,c.m=a.m;
        for (int i=1;i<=c.n;++i){
            for (int j=1;j<=c.m;++j){
                c.g[i][j]=a.g[i][j]+b.g[i][j];
                if (c.g[i][j]>=mod && isMod) c.g[i][j]%=mod;
            }
        }
        return c;
    }
    friend M operator * (M a,M b){
        M c;
        memset(c.g,0,sizeof c.g);
        c.n=a.n,c.m=b.m;
        for (int i=1;i<=c.n;++i){
            for (int j=1;j<=c.m;++j){
                for (int k=1;k<=a.m;++k){
                    c.g[i][j]+=a.g[i][k]*b.g[k][j];
                    if (c.g[i][j]>=mod && isMod) c.g[i][j]%=mod;
                }
            }
        }
        return c;
    }
    void initI(int N){
        memset(g,0,sizeof g);
        n=m=N;
        for (int i=1;i<=n;++i){
            g[i][i]=1;
        }
    }
    void init(int N,int M){
        n=N,m=M;
        for (int i=1;i<=n;++i){
            for (int j=1;j<=m;++j){
                scanf("%lld",&g[i][j]);
            }
        }
    }
    void out(){
        for (int i=1;i<=n;++i){
            for (int j=1;j<=m;++j){
                printf("%lld ",g[i][j]);
            }
            puts("");
        }
    }
}I;  //单位矩阵需要初始化

M Mpow(M a,ll b){  //矩阵快速幂
    M c=I,tmp=a;
    if (b==0) return c;
    for (;b;b>>=1){
        if (b&1){
            c=c*tmp;
        }
        tmp=tmp*tmp;
    }
    return c;
}

M Mpowsum(M &a,ll b){  //矩阵求幂累加和
    if (b==1) return a;
    if (b&1) return Mpow(a,b)+Mpowsum(a,b-1);
    else return (Mpow(a,b/2)+I)*Mpowsum(a,b/2);
}

int main(){
    I.initI(n);
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/107/