利用快速幂进行矩阵乘法运算

好的，以下是一个简单的实现方式：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int row;
    int col;
    int** data;
} Matrix;

Matrix* createMatrix(int row, int col) {
    Matrix* mat = (Matrix*)malloc(sizeof(Matrix));
    mat->row = row;
    mat->col = col;
    mat->data = (int**)malloc(sizeof(int*) * row);
    for(int i = 0; i < row; i++) {
        mat->data[i] = (int*)malloc(sizeof(int) * col);
        for(int j = 0; j < col; j++) {
            mat->data[i][j] = 0;
        }
    }
    return mat;
}

void destroyMatrix(Matrix* mat) {
    for(int i = 0; i < mat->row; i++) {
        free(mat->data[i]);
    }
    free(mat->data);
    free(mat);
}

void printMatrix(Matrix* mat) {
    for(int i = 0; i < mat->row; i++) {
        for(int j = 0; j < mat->col; j++) {
            printf("%d ", mat->data[i][j]);
        }
        printf("\n");
    }
}

Matrix* multiply(Matrix* mat1, Matrix* mat2) {
    if(mat1->col != mat2->row) {
        printf("Error: invalid matrix size.\n");
        return NULL;
    }
    int row = mat1->row;
    int col = mat2->col;
    int k = mat1->col;
    Matrix* res = createMatrix(row, col);
    for(int i = 0; i < row; i++) {
        for(int j = 0; j < col; j++) {
            int sum = 0;
            for(int t = 0; t < k; t++) {
                sum += mat1->data[i][t] * mat2->data[t][j];
            }
            res->data[i][j] = sum;
        }
    }
    return res;
}

Matrix* fastPow(Matrix* mat, int n) {
    if(n == 0) {
        Matrix* res = createMatrix(mat->row, mat->col);
        for(int i = 0; i < mat->row; i++) {
            res->data[i][i] = 1;
        }
        return res;
    }
    if(n == 1) {
        return mat;
    }
    Matrix* temp = fastPow(mat, n/2);
    Matrix* res = multiply(temp, temp);
    destroyMatrix(temp);
    if(n % 2 == 1) {
        Matrix* temp2 = multiply(res, mat);
        destroyMatrix(res);
        res = temp2;
    }
    return res;
}

int main() {
    int n;
    printf("Please enter the size of the matrix and the power:\n");
    scanf("%d", &n);
    Matrix* mat = createMatrix(n, n);
    printf("Please enter the elements of the matrix:\n");
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            scanf("%d", &mat->data[i][j]);
        }
    }
    int m;
    printf("Please enter the power:\n");
    scanf("%d", &m);
    Matrix* res = fastPow(mat, m);
    printf("The result is:\n");
    printMatrix(res);
    destroyMatrix(mat);
    destroyMatrix(res);
    return 0;
}

该代码中，我们定义了 `Matrix` 结构体来表示矩阵，并实现了矩阵的创建、销毁、打印和乘法运算等操作。在矩阵乘法的实现中，我们使用了普通的乘法算法，时间复杂度为 $O(n^3)$。而快速幂方法则可以将矩阵的幂运算优化到 $O(n^3 \log m)$ 的时间复杂度，其中 $m$ 表示幂的指数。具体实现中，我们利用递归的方式将指数不断折半，从而实现更高效的计算。需要注意的是，由于矩阵乘法的运算需要使用动态内存分配，因此在使用完毕后需要及时销毁对应的矩阵。