KY191 矩阵幂

算法内容

本文件实现牛客 KY191「矩阵幂」的一个基础版本。程序读取矩阵阶数 n 和幂次 k，再读取 n 阶矩阵并输出矩阵的 k 次幂。

mul 完成普通矩阵乘法，并把结果写回第一个矩阵；matPow 根据 pow 的取值执行固定次数的乘法。当前实现只显式处理 1 到 5 次幂，适合题目幂次范围较小或练习矩阵乘法流程的场景。矩阵乘法单次时间复杂度 O(n^3)。如果 k 更大，通常需要改为快速幂，将复杂度优化为 O(n^3 log k)。

算法实现

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<unordered_map>

using namespace std;

void mul(vector<vector<int>>& a, const vector<vector<int>> b, int n) {
    for(int i = 0; i < n; i++) {
        vector<int> ta;
        for(int j  = 0; j < n; j++) {
            int m = 0;
            for(int k = 0; k < n; k++) {
                m += a[i][k] * b[k][j];
            }
            ta.push_back(m);
        }
        a[i] = ta;
    }
}

void matPow(int n, vector<vector<int>>& res, const vector<vector<int>>& arr, int pow) {
    switch(pow) {
        case 1:
            break;
        case 2:
            mul(res, arr, n);
            break;
        case 3:
            mul(res, arr, n);
            mul(res, arr, n);
            break;
        case 4:
            mul(res, arr, n);
            mul(res, res, n);
            break;
        case 5:
            mul(res, arr, n);
            mul(res, res, n);
            mul(res, arr, n);
            break;
    }
}
int main() {
    int n, k;
    while(scanf("%d%d", &n, &k) != EOF){
        vector<vector<int>> arr(n, vector<int>(n, 0));
        vector<vector<int>> res(n, vector<int>(n, 0));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int t;
                scanf("%d", &t);
                res[i][j] = t;
                arr[i][j] = t;
            }
        }
        matPow(n, res, arr, k);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n-1; j++) {
                printf("%d ", res[i][j]);
            }
            printf("%d\n", res[i][n-1]);
        }
        
    }
    return 0;
}