Matrix multiplication hdu4920

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 0 1 2 1

1，忽视0 去做。

 1 #include"stdio.h"
 2 #include"string.h"
 3 int a[801][801],b[801][801];
 4 int a1[801][801],b1[801][801];
 5 int c[801][801];
 6 int main()
 7 {
 8     int n,i,j,k;
 9     while(scanf("%d",&n)==1)
10     {
11         memset(a,0,sizeof(a));
12         memset(b,0,sizeof(b));
13         memset(c,0,sizeof(c));
14         memset(a1,0,sizeof(a1));
15         memset(b1,0,sizeof(b1));
16         for(i=1;i<=n;i++)
17             for(j=1;j<=n;j++)
18             {
19                 scanf("%d",&a[i][j]);
20                 a[i][j]%=3;
21             }
22         for(i=1;i<=n;i++)
23             for(j=1;j<=n;j++)
24             {
25                 scanf("%d",&b[i][j]);
26                 b[i][j]%=3;
27             }
28         for(i=1;i<=n;i++)
29         {
30             int pre=-1;
31             for(j=n;j>=0;j--)
32             {
33                 a1[i][j]=pre;
34                 if(a[i][j])
35                     pre=j;
36             }
37         }
38         for(i=1;i<=n;i++)
39         {
40             int pre=-1;
41             for(j=n;j>=0;j--)
42             {
43                 b1[i][j]=pre;
44                 if(b[i][j])
45                     pre=j;
46             }
47         }
48         for(i=1;i<=n;i++)
49             for(j=a1[i][0];j+1;j=a1[i][j])
50                 for(k=b1[j][0];k+1;k=b1[j][k])
51                     c[i][k]+=a[i][j]*b[j][k];
52         for(i=1;i<=n;i++)
53         {
54             for(j=1;j<n;j++)
55                 printf("%d ",c[i][j]%3);
56             printf("%d
",c[i][j]%3);
57         }
58     }
59     return 0;
60 }

我们知道内存中二维数组是以行为单位连续存储的，逐列访问将会每次跳1000*4(bytes)。根据cpu cache的替换策略，将会有大量的cache失效。

时间居然会相差很多。可见利用好cpu cache优化我们的程序，是非常有必要掌握的技能。
平时写程序时，也应当尽量使cpu对内存的访问，是尽可能连续的

/*
    Name: Matrix multiplication
    Copyright: Shangli Cloud
    Author: Shangli Cloud
    Date: 05/08/14 20:46
    Description: 转置 
*/
/*
#include"iostream"
#include"cstdio"
#include"cstring"
using namespace std;
const int ms=801;
const int mod=3;
*/
#include"stdio.h"
#include"string.h"
//int a[ms][ms],b[ms][ms],c[ms][ms];
#define mod 3
int a[801][801],b[801][801],c[801][801];
int main()
{
    int n,x,i,j,k;
    while(scanf("%d",&n)==1)
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                scanf("%d",&x);
                a[i][j]=x%mod;
            }
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                scanf("%d",&x);
                b[j][i]=x%mod;
            }
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                c[i][j]=0;
                for(k=1;k<=n;k++)
                {
                    //c[i][j]+=a[i][k]*b[j][k]%mod;多了个mod就超时， 
                    c[i][j]+=a[i][k]*b[j][k];//1656ms,多个Mod就超过2s. 
                }
            if(j<n)
                printf("%d ",c[i][j]%mod);
            else
                printf("%d
",c[i][j]%mod);
            }
    }
    return 0;
}