题解 | #矩阵幂#

#include<iostream>
using namespace std;


/*
* 数字快速幂，初始值为1
* 矩阵快速幂，初始值为单位矩阵
*/

struct Matrix {
    int matrix[10][10];
    int col, row;
    Matrix(int r, int c): row(r), col(c) {}
};

void printMat(Matrix& ans) {
    //printf("row:%d;col:%d\n",ans.row,ans.col);
    for (int i = 0; i < ans.col; i++) {
        for (int j = 0; j < ans.row; j++) {
            if (j == ans.row - 1) {
                printf("%d", ans.matrix[i][j]);
            } else {
                printf("%d ", ans.matrix[i][j]);
            }
        }
        printf("\n");
    }
}

Matrix Multiply(Matrix x, Matrix y) {
    Matrix res(x.row, y.col);
    for (int i = 0; i < res.row; i++) {
        for (int j = 0; j < res.col; j++) {
            res.matrix[i][j] = 0;
            for (int k = 0; k < x.col; k++) {
                res.matrix[i][j] += x.matrix[i][k] * y.matrix[k][j];
            }
        }
    }
    return res;
}

void FastExp(Matrix x, int k, Matrix& ans) {
    for (int i = 0; i < ans.row; i++) {
        for (int j = 0; j < ans.col; j++) {
            //调了半天，最后发现是这里写成了i<ans.col
            if (i == j) {
                ans.matrix[i][j] = 1;
            } else {
                ans.matrix[i][j] = 0;
            }
        }
    }
    while (k != 0) {
        if (k % 2 == 1) {
            ans = Multiply(ans, x);
        }
        k /= 2;
        x = Multiply(x, x);
    }
}



int main() {
    int n, k;
    while (scanf("%d %d", &n, &k) != EOF) {
        //int a[n][n],ans[n][n];    //全局数组这样好像不行，内部的居然可以
        Matrix x(n, n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &x.matrix[i][j]);
            }
        }
        Matrix ans(n, n);
        FastExp(x, k, ans);
        printMat(ans);
    }
    return 0;
}

1. 写循环的时候不要掉以轻心，一些奇怪的错误可能很久都调不出来
2. 结构体可以直接赋值，也可以写构造函数，也可以引用传参！！还是很好用的~