题解 | #矩阵幂#

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;

/**
 * 矩阵维数
 */
const int DIMENSION = 10;

/**
 * 矩阵
 */
struct Matrix {
    int row;    //矩阵的行
    int col;    //矩阵的列
    int matrix[DIMENSION][DIMENSION];     //二维数组模拟矩阵

    //构造函数
    Matrix(int row, int col) {
        this->row = row;
        this->col = col;
    }
};

/**
 * 矩阵乘法
 * @param x
 * @param y
 * @return
 */
Matrix multiply(Matrix x, Matrix y);

/**
 * 矩阵求幂
 * @param x
 * @return
 */
Matrix quickPower(Matrix x, int n);

/**
 * 打印矩阵
 * @param x
 */
void printMatrix(Matrix x);


/**
 * 矩阵幂--北京邮电大学
 * @return
 */
int main() {
    int n;
    int k;
    while (cin >> n >> k) {
        Matrix x = Matrix(n, n);
        for (int i = 0; i < x.row; ++i) {
            for (int j = 0; j < x.col; ++j) {
                cin >> x.matrix[i][j];
            }
        }
        Matrix ans = quickPower(x, k);
        printMatrix(ans);
    }
    return 0;
}

Matrix multiply(Matrix x, Matrix y) {
    //矩阵乘法结果是x的行和y的列
    Matrix ans(x.row, y.col);
    for (int i = 0; i < ans.row; ++i) {
        for (int j = 0; j < ans.col; ++j) {
            //先初始化为0
            ans.matrix[i][j] = 0;
            /*
             * 根据矩阵相乘的规则
             * matrix[i][j] = x的第i行与y的第j列对应的乘积和
             */
            for (int k = 0; k < x.col; ++k) {
                ans.matrix[i][j] += x.matrix[i][k] * y.matrix[k][j];
            }
        }
    }
    return ans;
}

void printMatrix(Matrix x) {
    //注意题目明确的输出格式
    for (int i = 0; i < x.row; ++i) {
        for (int j = 0; j < x.col; ++j) {
            if (j == 0) {
                //第一列不带空格
                cout << x.matrix[i][j];
            } else {
                //非第一列带前置空格
                cout << " " << x.matrix[i][j];
            }
        }
        cout << endl;
    }
}

Matrix quickPower(Matrix x, int n) {
    Matrix ans = Matrix(x.row, x.col);
    //初始化为单位阵
    for (int i = 0; i < ans.row; ++i) {
        for (int j = 0; j < ans.col; ++j) {
            if (i == j) {
                ans.matrix[i][j] = 1;
            } else {
                ans.matrix[i][j] = 0;
            }
        }
    }

    /*
     * 求快速幂的方法
     */
    while (n != 0) {
        if (n % 2 == 1) {
            ans = multiply(ans, x);
        }
        n = n >> 1;
        x = multiply(x, x);
    }

    return ans;
}