矩阵快速幂

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define N 100
#define ll long long 
struct Mat{
    ll mat[N][N];
};
void showmat(Mat a)
{
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
            printf("%lld ",a.mat[i][j]);
        printf("\n");
    }
}
void Init(Mat &b)//初始化为单位矩阵 ,要引用 
{
    int i, j, k;
    for(i = 0; i < 3; ++i) {
        for(j = 0; j < 3; ++j) 
        {
            b.mat[i][j] = (i == j);//简略的写法 
        }
    }
}
Mat MatMul(Mat a,Mat b)
{
    Mat c;
    memset(c.mat, 0, sizeof(c.mat));
    int i, j, k;
    for(i = 0; i < 3; ++i) {
        for(j = 0; j < 3; ++j) 
        {
            for(k = 0; k < 3; ++k) 
            {
                c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
            }
        }
    }
    return c;
}
Mat MATLAB(Mat a,int n)//核心代码,例A^156=(A^4)*(A^8)*(A^16)*(A^128) 
{
    Mat b;
    Init(b);
    while(n)
    {
        if(n&1)
            b = MatMul(b,a);
        n >>= 1;//右移
        a = MatMul(a,a); 
    }
    return b;
}
int main()
{
    int n;
    Mat a,b;
    scanf("%d",&n);
    memset(a.mat,0,sizeof(a.mat));
    memset(b.mat,0,sizeof(b.mat));
    //生成三维随机矩阵 
    srand(time(0));//随机种子---stdlib.h 
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            a.mat[i][j] = rand()%100;
    printf("随机矩阵为：\n");
    showmat(a);
    b = MATLAB(a,n);
    printf("%d次幂所得结果矩阵为:\n",n);
    showmat(b);
    return 0;
}