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

1

1

2

0 1

2 3

4 5

6 7

Sample Output

0 0 1 2 1

1，忽视0  去做。

 #include"stdio.h"
 #include"string.h"
 int a[][],b[][];
 int a1[][],b1[][];
 int c[][];
 int main()
 {
     int n,i,j,k;
     while(scanf("%d",&n)==)
     {
         memset(a,,sizeof(a));
         memset(b,,sizeof(b));
         memset(c,,sizeof(c));
         memset(a1,,sizeof(a1));
         memset(b1,,sizeof(b1));
         for(i=;i<=n;i++)
             for(j=;j<=n;j++)
             {
                 scanf("%d",&a[i][j]);
                 a[i][j]%=;
             }
         for(i=;i<=n;i++)
             for(j=;j<=n;j++)
             {
                 scanf("%d",&b[i][j]);
                 b[i][j]%=;
             }
         for(i=;i<=n;i++)
         {
             int pre=-;
             for(j=n;j>=;j--)
             {
                 a1[i][j]=pre;
                 if(a[i][j])
                     pre=j;
             }
         }
         for(i=;i<=n;i++)
         {
             int pre=-;
             for(j=n;j>=;j--)
             {
                 b1[i][j]=pre;
                 if(b[i][j])
                     pre=j;
             }
         }
         for(i=;i<=n;i++)
             for(j=a1[i][];j+;j=a1[i][j])
                 for(k=b1[j][];k+;k=b1[j][k])
                     c[i][k]+=a[i][j]*b[j][k];
         for(i=;i<=n;i++)
         {
             for(j=;j<n;j++)
                 printf("%d ",c[i][j]%);
             printf("%d\n",c[i][j]%);
         }
     }
     return ;
 }

我们知道内存中二维数组是以行为单位连续存储的，逐列访问将会每次跳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[][],b[][],c[][];
int main()
{
    int n,x,i,j,k;
    while(scanf("%d",&n)==)
    {
        for(i=;i<=n;i++)
            for(j=;j<=n;j++)
            {
                scanf("%d",&x);
                a[i][j]=x%mod;
            }
        for(i=;i<=n;i++)
            for(j=;j<=n;j++)
            {
                scanf("%d",&x);
                b[j][i]=x%mod;
            }
        for(i=;i<=n;i++)
            for(j=;j<=n;j++)
            {
                c[i][j]=;
                for(k=;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\n",c[i][j]%mod);
            }
    }
    return ;
}