HDU 4920 Matrix multiplication 矩阵相乘。稀疏矩阵

Matrix multiplication

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1775 Accepted Submission(s): 796

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.

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 A_ij. The next n lines describe the matrix B in similar format (0≤A_ij,B_ij≤10⁹).

Output

For each tests:

Print n lines. Each of them contain n integers -- the matrix A×B in similar format.

Sample Input

0 1

2 3

4 5

6 7

Sample Output

0 1

2 1

Author

Xiaoxu Guo (ftiasch)

Source

2014 Multi-University Training Contest 5

Recommend

We have carefully selected several similar problems for you: 4919 4918 4917 4916 4915

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 using namespace std;
 6 
 7 struct Matrix
 8 {
 9     int mat[801][801];
10 }hxl,tom,now;
11 void solve(int n)
12 {
13     int i,j,k;
14     for(i=1;i<=n;i++)
15     {
16         for(k=1;k<=n;k++)
17         {
18             if(hxl.mat[i][k]==0) continue;
19             for(j=1;j<=n;j++)
20             {
21                 now.mat[i][j] = now.mat[i][j] + hxl.mat[i][k]*tom.mat[k][j];
22             }
23         }
24     }
25     for(i=1;i<=n;i++)
26     {
27         for(j=1;j<=n;j++)
28         {
29             if(j==1)printf("%d",now.mat[i][j]%3);
30             else printf(" %d",now.mat[i][j]%3);
31         }
32         printf("
");
33     }
34 }
35 int main()
36 {
37     int n;
38     int i,j;
39     while(scanf("%d",&n)>0)
40     {
41         for(i=1;i<=n;i++)
42             for(j=1;j<=n;j++)
43             {
44                 scanf("%d",&hxl.mat[i][j]);
45                 hxl.mat[i][j]%=3;
46                 now.mat[i][j] = 0;
47             }
48         for(i=1;i<=n;i++)
49             for(j=1;j<=n;j++)
50             {
51                 scanf("%d",&tom.mat[i][j]);
52                 tom.mat[i][j]%=3;
53             }
54         solve(n);
55 
56     }
57     return 0;
58 }