Matrix multiplication
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 820 Accepted Submission(s): 328
Problem Description
Given two matrices A and B of size n×n, find the product of them.
bobo hates big integers. So you are only asked to find the result modulo 3.
bobo hates big integers. So you are only asked to find the result modulo 3.
Input
The input consists of several tests. For each tests:
The first line contains n (1≤n≤800). Each of the following n lines contain n integers -- the description of the matrix A. The j-th integer in the i-th line equals Aij. The next n lines describe the matrix B in similar format (0≤Aij,Bij≤109).
The first line contains n (1≤n≤800). Each of the following n lines contain n integers -- the description of the matrix A. The j-th integer in the i-th line equals Aij. The next n lines describe the matrix B in similar format (0≤Aij,Bij≤109).
Output
For each tests:
Print n lines. Each of them contain n integers -- the matrix A×B in similar format.
Print n lines. Each of them contain n integers -- the matrix A×B in similar format.
Sample Input
1
0
1
2
0 1
2 3
4 5
6 7
Sample Output
0
0 1
2 1
Author
Xiaoxu Guo (ftiasch)
Source
Mean:
给你两个矩阵，计算两个矩阵的积。
nalyse:
很多人认为这题用暴力过不了，时间复杂度为O(n^3),800^3=512000000，差不多要接近于10^9了，可能是hdu的评测速度给力吧，再加上这题是单点评测，每个评测点的时限都有2000ms，所以说暴力过了也实属正常。
Time complexity：O(n^3)
Source code：
#include<stdio.h>
int a[800][800],b[800][800],c[800][800],n,i,j,k;
int main(){
while(scanf("%d",&n)!=EOF){
for(i=0;i<n;++i)
for(j=0;j<n;++j)
scanf("%d",&a[i][j]),a[i][j]%=3;
for(i=0;i<n;++i)
for(j=0;j<n;++j)
scanf("%d",&b[i][j]),b[i][j]%=3;
for(i=0;i<n;++i)
for(j=0;j<i;++j)
k=b[i][j],b[i][j]=b[j][i],b[j][i]=k;
for(i=0;i<n;++i)
for(j=0;j<n;++j){
c[i][j]=0;
for(k=0;k<n;++k)
c[i][j]+=a[i][k]*b[j][k];
c[i][j]%=3;
}
for(i=0;i<n;++i)
for(j=0;j<n;++j)
printf(j==n-1?"%d\n":"%d ",c[i][j]);
}
return 0;
}