第一行:两个整数n(2<=n<=10)、k(1<=k<=5),两个数字之间用一个空格隔开,含义如上所示。 接下来有n行,每行n个正整数,其中,第i行第j个整数表示矩阵中第i行第j列的矩阵元素Pij且(0<=Pij<=10)。另外,数据保证最后结果不会超过10^8。
对于每组测试数据,输出其结果。格式为: n行n列个整数,每行数之间用空格隔开,注意,每行最后一个数后面不应该有多余的空格。
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 <iostream>
#include <cstdio>
#include <cstring>
const int maxn = 20; //矩阵最大行列数
using namespace std;
struct Mat
{
int mat[maxn][maxn]; //矩阵
int row, col; //矩阵行列数
};
Mat mod_mul(Mat a, Mat b, int p) //矩阵乘法
{
Mat ans;
ans.row = a.row;
ans.col = b.col;
memset(ans.mat, 0, sizeof(ans.mat));
for (int i = 0; i < ans.row; i++)
for (int j = 0; j < ans.col; j++)
for (int k = 0; k < a.col; k++)
{
ans.mat[i][j] += a.mat[i][k] * b.mat[k][j];
ans.mat[i][j] %= p;
}
return ans;
}
Mat mod_pow(Mat a, int k, int p) //矩阵快速幂
{
Mat ans;
ans.row = a.row;
ans.col = a.col;
for (int i = 0; i < a.row; i++)
for (int j = 0; j < a.col; j++)
ans.mat[i][j] = (i == j);
while (k)
{
if (k & 1)
ans = mod_mul(ans, a, p);
a = mod_mul(a, a, p);
k >>= 1;
}
return ans;
}
int main()
{
// freopen("in.txt", "r", stdin);
Mat m;
int n, k;
while (~scanf("%d%d", &n, &k))
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &m.mat[i][j]);
m.col = m.row = n;
Mat ans = mod_pow(m, k, 10e8);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (j != 0)
printf(" ");
printf("%d", ans.mat[i][j]);
}
printf("\n");
}
}
return 0;
}
#include<stdio.h> int main() { int i,j,n,m,k,a[20][20],result[20][20]; while(scanf("%d%d",&n,&m)!=EOF) { for(i=0;i<n;i++) for(j=0;j<n;j++) { scanf("%d",&a[i][j]); result[i][j]=a[i][j]; } while(--m) { int c[20][20]={0};//过渡数组 for(i=0;i<n;i++) for(j=0;j<n;j++) for(k=0;k<n;k++) c[i][j]+=result[i][k]*a[k][j];//重点 for(i=0;i<n;i++) for(j=0;j<n;j++) result[i][j]=c[i][j]; } for(i=0;i<n;i++) { for(j=0;j<n;j++) printf("%d ",result[i][j]); printf("\n"); } } return 0; }
#include<bits/stdc++.h>
int main(){
int n,k;
while(scanf("%d %d",&n,&k)!=EOF){
int a[10][10],b[10][10],c[10][10];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
scanf("%d",&a[i][j]);
c[i][j]=a[i][j];
}
for(int i=0;i<k-1;i++){
for(int l=0;l<n;l++)
for(int j=0;j<n;j++)
b[l][j]=c[l][j];
for(int j=0;j<n;j++)
for(int l=0;l<n;l++){
int temp=0;
for(int m=0;m<n;m++)
temp+=a[j][m]*b[m][l];
c[j][l]=temp;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
printf("%d ",c[i][j]);
printf("\n");
}
}
}
#include<stdio.h> #include<string.h> typedef long long ll; int main(){ ll a[100][100]; ll b[100][100]; ll c[100][100]; int n,k; scanf("%d%d",&n,&k); for(int i=0;i<n;i++) for(int j=0;j<n;j++){ scanf("%lld",&a[i][j]); b[i][j]=a[i][j];//将a赋值给b } while(k-1){//矩阵k次方 memset(c,0,sizeof(c));//要每次将c置0,c暂存结果 for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int m=0;m<n;m++) c[i][j]+=b[i][m]*a[m][j];//保存每一次结果 for(int i=0;i<n;i++) for(int j=0;j<n;j++) b[i][j]=c[i][j];//b存最终结果 k--; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(j!=0) printf(" "); printf("%lld",b[i][j]); } printf("\n"); } return 0; }
#include <stdio.h> #include <stdlib.h> void matrix_multiply(int *a,int *b,int *c,int n) // a*b=c { for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { c[n*i+j]=0; for(int k=0; k<n; k++) { c[n*i+j]+=a[n*i+k]*b[n*k+j]; } } } } int main() { int n,k; while(scanf("%d%d",&n,&k)!=EOF) { int *a=(int*)malloc(sizeof(int)*n*n); int *b=(int*)malloc(sizeof(int)*n*n); for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { scanf("%d",&a[n*i+j]); b[n*i+j]=a[n*i+j]; } } int *t=(int*)malloc(sizeof(int)*n*n); for(int i=2; i<=k; i++) { matrix_multiply(b,a,t,n); for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { b[n*i+j]=t[n*i+j]; } } } for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { printf("%d ",b[n*i+j]); } printf("\n"); } } return 0; }
#include<iostream> using namespace std; #define max_len 10 //第一次不细心,没咋看输出格式-_-晕 int a[max_len][max_len];//用全局变量以保证函数运行后,变量的值不会丢失 int b[max_len][max_len];//保存最初始矩阵的值 void mutiple(int a[max_len][max_len],int n) { int sum[n][n]; for(int i = 0;i < n;i++) for(int j = 0;j < n;j++) { sum[i][j] = 0; for(int k = 0;k < n;k++) { sum[i][j] += a[i][k] * b[k][j]; //计算的重点,用j进行列的更新 } } for(int i = 0;i < n;i++) for(int j = 0;j < n;j++) a[i][j] = sum[i][j];//对a数组进行重新赋值,以保存计算的结果 } int main(void) { int n,k; while(cin >> n >> k) { for(int i = 0;i < n;i++) for(int j = 0;j < n;j++) cin >> a[i][j]; for(int i = 0;i < n;i++) for(int j = 0;j < n;j++) b[i][j] = a[i][j]; for(int i = 1;i < k;i++)//进行K次幂运算 mutiple(a,n); for(int i = 0;i < n;i++) { //cout << endl; for(int j = 0;j < n;j++) cout << a[i][j] << ' '; cout << endl; } } return 0; }
#include <iostream> using namespace std; /*给定一个n*n的矩阵,求该矩阵的k次幂,即P^k。(2<=n<=10)、k(1<=k<=5) Pij且(0<=Pij<=10)。另外,数据保证最后结果不会超过10^8*/ class matrix { public: //matrix() {}//无参构造 matrix(int r, int c)//有参构造 { this->row = r; this->col = c; this->mat = new int*[r];//初始化矩阵空间 for (int k = 0; k < r; k++) this->mat[k] = new int[c]; } matrix(const matrix &m)//因为类开辟了堆区空间,重写拷贝构造 { this->row = m.row; this->col = m.col; this->mat = new int*[row]; for (int i = 0; i < this->row; i++) { this->mat[i] = new int[col]; for (int j = 0; j < this->col; j++) this->mat[i][j] = m.mat[i][j]; } } matrix& operator=(const matrix& m)//重载赋值操作符 { this->row = m.row; this->col = m.col; if (mat == NULL)//如果堆区为空,则开辟 { this->mat = new int* [row]; for (int k = 0; k < row; k++) mat[k] = new int[col]; } for (int i = 0; i < this->row; i++) { for (int j = 0; j < this->col; j++) this->mat[i][j] = m.mat[i][j]; } return *this; } void init_matrix() { this->mat = new int* [row];//初始化矩阵空间 for (int i = 0; i < this->row; i++) { this->mat[i] = new int[col]; for (int j = 0; j < this->col; j++) cin >> this->mat[i][j];//输入矩阵 } } void dispaly() { for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) cout << this->mat[i][j] << " "; cout << endl; } } ~matrix()//析构堆区空间 { for (int i = 0; i < this->row; i++) if (mat[i] != NULL) { delete[] mat[i]; mat[i] = NULL;//防止野指针 } if (mat != NULL) { delete[] mat; mat = NULL; } } //private://类含有指向堆区的指针成员,会产生深拷贝问题,要重写拷贝构造和=赋值操作符 int** mat; int row, col; }; matrix operator*(const matrix &a, const matrix &b) { if (a.row != b.col || a.col != b.row) { cout << "矩阵大小不匹配" << endl; exit(0); } matrix result(a.row, a.col); for (int k = 0; k < a.row; k++) { for (int i = 0; i < a.row; i++) { int sum = 0; for (int j = 0; j < a.col; j++) sum += a.mat[k][j] * b.mat[j][i]; result.mat[k][i] = sum; } } return result; } matrix matrix_pow(matrix &a, int k) //矩阵快速幂 { matrix ans(a.row ,a.col); for (int i = 0; i < ans.row; i++) for (int j = 0; j < ans.col; j++) if (i == j) ans.mat[i][j] = 1; else ans.mat[i][j] = 0; while (k != 0) { if (k % 2 == 1) ans = ans * a; a = a * a; k /= 2; } return ans; } void test1() { int n, k; while (cin >> n >> k) { matrix m(n,n); m.init_matrix(); //matrix ans(n,n); matrix ans = matrix_pow(m, k); ans.dispaly(); } } int main() { test1(); return 0; }
import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNext()) { int size = scanner.nextInt(), pow = scanner.nextInt(); int[][] num = new int[size][size]; for(int j = 0; j < num.length; j++) for(int k = 0; k < num.length; k++) num[j][k] = scanner.nextInt(); int[][] nums = powSquel(num, pow); for(int j = 0; j < nums.length; j++) { for(int k = 0; k < nums.length; k++) { System.out.print(nums[j][k]); if(k != nums.length - 1) System.out.print(" "); } System.out.println(); } } } private static int[][] powSquel(int[][] num, int pow) { int[][] nums = new int[num.length][num.length]; nums = num; while(pow > 1) { int[][] nums1 = new int[num.length][num.length]; for(int i = 0; i < num.length; i++) for(int j = 0; j < num.length; j++) for(int k = 0; k < num.length; k++) nums1[i][j] += nums[i][k] * num[k][j]; nums = nums1; pow--; } return nums; } }
#include <iostream> #include <array> using namespace std; typedef array<array<int,10>,10> node; node data,ans,temp; int n,k; node mul(const node& x1,const node& x2){//矩阵乘法 for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ int sum=0; for(int k=0;k<n;k++) sum = sum +x1[i][k]*x2[k][j]; temp[i][j]= sum; } } return temp; } void init(){ for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i==j) ans[i][j]=1; else ans[i][j]=0; } int main(){ while (cin>>n>>k) { init(); for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>data[i][j]; while(k!=0){ if(k%2) ans = mul(ans,data); k=k/2; data = mul(data,data); } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(j==n-1) cout<<ans[i][j]; else cout<<ans[i][j]<<' '; } cout<<endl; } } return 0; }矩阵快速幂,把一次矩阵乘法看做一个基本单位,时间复杂度logn
//思路,矩阵的幂次,由于我刚在练手快速幂所以想到矩阵的幂能不能也用快速幂的方法,把矩阵整体当成一个数来求幂 //这个时候想到重载*号,内部细节重载,外部看起来和普通*号的用法一样 //重载运算符号可以少写几个函数 原谅我的偷懒 嘿嘿嘿 #include<iostream> using namespace std; struct shu//定义一个结构保存数组和重载*号 { int a[10][10] = {0};//全部置零 shu operator*(const shu& c)//重载*号 { shu temp; for (int i = 0; i < 10; i++)//经典的矩阵乘法的3重循环 for (int j = 0; j < 10; j++) for (int k = 0; k < 10; k++) temp.a[i][j] += a[i][k] * c.a[k][j];//一行乘一列 return temp; } }; int main() { int n, k; while (cin >> n >> k) { shu m,temp;//快速幂中 我们会使用一个temp来保存我们最后求到的结果,且temp初始化=1; for (int i = 0; i < n; i++)//那么矩阵中相当于普通整数的1的是什么呢 答案是单位阵 temp.a[i][i] = 1;//所以这里先定义一个单位阵作为‘1‘;主线为1,其余为0的矩阵 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> m.a[i][j]; while (k)//这里就是经典的快速幂的方法了 { if (k % 2 == 1) { temp = temp*m; } k /= 2; m = m * m; } for (int i = 0; i < n; i++)//注意只遍历到n-1过,过了n-1的元素全是0了 { for (int j = 0; j < n; j++) cout << temp.a[i][j] << " "; cout << endl; } } }
#include<iostream> (720)#include<vector> #include<algorithm> using namespace std; vector<vector<int>> cro_matrix(vector<vector<int>> a,vector<vector<int>> b,int n){ vector<vector<int>> sum(n,vector<int>(n)); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ sum[i][j] = 0; for(int k=0;k<n;k++) sum[i][j]+=a[i][k]*b[k][j]; } } return sum; } vector<vector<int>> cur_pow_matrix(vector<vector<int>> a,int n,int k){ if(k==2){ return cro_matrix(a,a,n); } else{ if(k==1){ return a; } else{ vector<vector<int>> b( cur_pow_matrix(a,n,k/2)); b = cro_matrix(b,b,n); if(k%2==1){ b = cro_matrix(a,b,n); } return b; } } } int main(void){ int n,k; while(cin>>n>>k){ int temp; vector<vector<int>> a(n,vector<int>(n)); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>temp; a[i][j] = temp; } } vector<vector<int>> b(cur_pow_matrix(a,n,k)); 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; } } return 0; }
/* 开始在想这可怎么算,每次一个n^3 灵光一现,快速幂啊 author@RH time:2019/9/7/23:48 */ #include <stdio.h> using namespace std; int matrix[10][10]; int c[10][10]; int result[10][10]; int n; int k; void mul(int(*a)[10], int(*b)[10]) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { c[i][j] = 0; for (int k = 0; k < n; k++) { c[i][j] += a[i][k] * b[k][j]; } } } return; } void copy(int (*a)[10], int (*b)[10]) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { a[i][j] = b[i][j]; } } } int main() { while (scanf("%d%d", &n, &k) != EOF) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &matrix[i][j]); result[i][j] = 0; } result[i][i] = 1; } while (k != 0) { if (k % 2 == 1) { mul(result, matrix); copy(result, c); } mul(matrix, matrix); copy(matrix, c); k /= 2; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { printf("%d ", result[i][j]); } printf("\n"); } } return 0; }
#include<stdio.h> int main(){ int i,j,k,n,t; int a[11][11]; int b[11][11]; int c[11][11]; while(scanf("%d%d",&n,&k)!=EOF){ for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ scanf("%d",&a[i][j]); b[i][j]=a[i][j]; c[i][j]=a[i][j]; } } for(t=1;t<k;t++){ for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ int sum=0; for(int r=1;r<=n;r++){ sum=sum+b[i][r]*a[r][j]; } c[i][j]=sum; } } for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ b[i][j]=c[i][j]; } } } for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(j==1){ printf("%d",b[i][j]); } else printf(" %d",b[i][j]); } printf("\n"); } } }
#include <iostream> #include <vector> using namespace std; int main(){ int n, k; while (cin >> n >> k){ int a[12][12] = { { 0 } }; int result[12][12] = { { 0 } }; for (int i = 0; i < n; i++){ result[i][i] = 1; } for (int i = 0; i<n; i++){ for (int j = 0; j<n; j++){ cin >> a[i][j]; } } for (int i = 0; i<k; i++){ int temp[12][12] = { { 0 } }; for (int j = 0; j<n; j++){ for (int k = 0; k<n; k++){ for (int l = 0; l<n; l++){ temp[j][k] += result[j][l] * a[l][k]; } } } for (int j = 0; j < n; j++){ for (int k = 0; k < n; k++){ result[j][k] = temp[j][k]; } } } for (int i = 0; i<n; i++){ for (int j = 0; j<n; j++){ cout << result[i][j] << " "; } cout << endl; } } }
#include<iostream> using namespace std; int main() { int n,k; while(cin>>n>>k) { int mat1[11][11],matrix[11][11]; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin>>matrix[i][j]; mat1[i][j]=matrix[i][j]; } } int mat2[11][11]; for(int i=0;i<11;i++) fill(mat2[i],mat2[i]+11,0); for(int q=2;q<=k;q++) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { for(int p=0;p<n;p++) mat2[i][j]+=(mat1[i][p]*matrix[p][j]); } } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { mat1[i][j]=mat2[i][j]; mat2[i][j]=0; } } } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cout<<mat1[i][j]; if(j!=n-1)cout<<' '; } cout<<endl; } } return 0; }
#include<stdio.h> int main(){ int n,k; while(scanf("%d%d",&n,&k)!=EOF){ int num[10][10]; int tmp1[10][10]; int ans[10][10]; for(int i=0;i<n;i++) for(int j=0;j<n;j++){ int tmp; scanf("%d",&tmp); num[i][j]=tmp; ans[i][j]=tmp; tmp1[i][j]=tmp; } while(k>1){ for(int i=0;i<n;i++) for(int j=0;j<n;j++){ int tmp=0; for(int x=0;x<n;x++){ tmp+=tmp1[i][x]*num[x][j]; } ans[i][j]=tmp; } for(int i=0;i<n;i++) for(int j=0;j<n;j++) tmp1[i][j]=ans[i][j]; k--; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(j==n-1) printf("%d",ans[i][j]); else printf("%d ",ans[i][j]); } printf("\n"); } } }