首页 > 代码库 > Matrix multiplication hdu4920

Matrix multiplication hdu4920

2024-07-16 00:27:53   218人阅读

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 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
0
1
2
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\n",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 3int 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\n",c[i][j]%mod);            }    }    return 0;}

 


联系
我们