C++(g++ 7.5.0) 解法, 执行用时: 197ms, 内存消耗: 2036K, 提交时间: 2022-08-06 11:12:57

#include<bits/stdc++.h>
using namespace std;
int n,k,mod;
struct Matrix
{
    int a[35][35];
};
Matrix m,unit;
Matrix add(Matrix x,Matrix y)
{
    Matrix ans;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        {
            ans.a[i][j]=0;
            ans.a[i][j]=(x.a[i][j]+y.a[i][j])%mod;
        }
    return ans;
}
Matrix multi(Matrix x,Matrix y)
{
    Matrix ans;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        {
            ans.a[i][j]=0;
            for(int k=0; k<n; k++)
                ans.a[i][j]=(ans.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
        }
    return ans;
}
Matrix mqmod(int l)
{
    Matrix p,q;
    p=m,q=unit;
    while(l)
    {
        if(l&1)q=multi(q,p);
        p=multi(p,p);
        l>>=1;
    }
    return q;
}
Matrix matrixsum(int k)
{
    if(k==1)return m;
    Matrix temp,tnow;
    temp=matrixsum(k/2);
    tnow=mqmod(k/2);
    temp=add(temp,multi(temp,tnow));
    if(k&1)//奇数的时候多加上A^k
        temp=add(mqmod(k),temp);
    return temp;
}
int main()
{
    scanf("%d%d%d",&n,&k,&mod);

    int q;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        {
            scanf("%d",&q);
            m.a[i][j]=q%mod;
            unit.a[i][j]=(i==j);
        }
    Matrix ans;
    ans=matrixsum(k);
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n-1; j++)
            printf("%d ",ans.a[i][j]);
        printf("%d\n",ans.a[i][n-1]);
    }
    return 0;
}

C++ 解法, 执行用时: 76ms, 内存消耗: 436K, 提交时间: 2022-05-27 16:24:56

//对矩阵进行求和
//矩阵套矩阵,开双倍的空间
//S(n)      1  1   S(0)
//A(n+1)    0  A1  A1
//共循环n次
//单位矩阵*矩阵=原矩阵
//所以这里的1为原矩阵
#include <bits/stdc++.h>
using namespace std;
#define M 75

int n,m,k,nn;
struct mat {
    int a[M][M];
    mat() {//清空
        for(int i=1;i<=nn;i++)
            for(int j=1;j<=nn;j++)
                a[i][j]=0;
    }
    mat operator*(const mat b) {
        mat c;
        for(int i=1;i<=nn;i++)
            for(int j=1;j<=nn;j++)
                for(int k=1;k<=nn;k++) {
                    c.a[i][j]+=a[i][k]*b.a[k][j];
                    c.a[i][j]%=m;
                }
        return c;
    }
}ans,c,A;//三个数组与上面依次对应

void qpow() {
    while(k) {
        if(k&1)A=c*A;
        c=c*c;
        k>>=1;
    }
}

int main() {
    cin>>n>>k>>m;
    nn=2*n;
    for(int i=n+1;i<=2*n;i++)
        for(int j=1;j<=n;j++) {
            cin>>A.a[i][j];
            c.a[i][j+n]=A.a[i][j];
        }
    for(int i=1;i<=n;i++)
        c.a[i][i]=c.a[i][i+n]=1;
    qpow();
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++)cout<<A.a[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}