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:
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).
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 ;
}