2012.计算机院.Problem B.矩阵幂

小鱼儿 2023-07-21 06:20 51阅读 0赞

**题目描述**  
给你一个n\*n的矩阵，求其矩阵的k次幂，即Pk  
**输入格式**  
第一行，一个整数T（0<T<=10），表示要求矩阵的个数。  
接下来有T组数据，每组数据格式如下：  
第一行：两个数据n（2<=n<=10）、k（1<=k<=5），两个数字之间用一个空格隔开，其中n表示状况空间的总数，k表示待求的转移概率矩阵的步数。接下来有n行n列个正整数，其中，第i行第j列表示pij，（0<=pij<=10）。另外，数据保证最后结果不会超过10^8。  
**输出格式**  
输出为T组数据。  
每组数据为已知矩阵的k次幂，格式为：  
n行n列个正整数，每行数之间用空格隔开，注意，每行最后一个数后面不应该有多余的空格。  
**输入样例**

3
    2 2
    9 8
    9 3
    3 3
    4 8 4
    9 3 0
    3 5 7
    5 2
    4 0 3 0 1
    0 0 5 8 5
    8 9 8 5 3
    9 6 1 7 8
    7 2 5 7 3

**输出样例**

153 96
    108 81
    1216 1248 708
    1089 927 504
    1161 1151 739
    47 29 41 22 16
    147 103 73 116 94
    162 108 153 168 126
    163 67 112 158 122
    152 93 93 111 97

#include<bits/stdc++.h>
    using namespace std;
    int main() { 
    	int T,n,k;
    	cin>>T;
    	while(T--) { 
    		cin>>n>>k;
    		int a[n][n];
    		int b[n][n];
    		int c[n][n];
    		for(int i=0; i<n; i++) { 
    			for(int j=0; j<n; j++) { 
    				cin>>a[i][j];
    				b[i][j]=a[i][j];
    			}
    		}
    		for(int cnt=0; cnt<k-1; cnt++) { 
    			for(int i=0; i<n; i++) { 
    				for(int j=0; j<n; j++) { 
    					int sum=0;
    					for(int p=0; p<n; p++) { 
    						sum+=b[i][p]*a[p][j];
    					}
    					c[i][j]=sum;
    				}
    			}
    			for(int i=0; i<n; i++) { 
    				for(int j=0; j<n; j++) { 
    					b[i][j]=c[i][j];
    				}
    			}
    		}
    		for(int i=0; i<n; i++) { 
    			for(int j=0; j<n; j++) { 
    				if(j==0){ 
    					cout<<b[i][j];
    				}else{ 
    					cout<<" "<<b[i][j];
    				}
    			}
    			cout<<endl;
    		}
    	}
    }