首页 > 代码库 > hdu 4920 Matrix multiplication （矩阵计算）

hdu 4920 Matrix multiplication （矩阵计算）

2024-07-15 23:34:28   221人阅读

题目链接

题意：给两个矩阵a， b, 计算矩阵a*b的结果对3取余。

分析：直接计算时间复杂度是O(n^3),会超时，但是下面第一个代码勉强可以水过，数据的原因。

 1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <cstring> 5 #include <cstdlib> 6 #include <algorithm> 7 const int maxn = 800+10; 8 using namespace std; 9 int n, a[maxn][maxn], b[maxn][maxn], c[maxn][maxn];10 11 int main()12 {13     int i, j, k;14     while(~scanf("%d", &n))15     {16         memset(a, 0, sizeof(a));17         memset(b, 0, sizeof(b));18         memset(c, 0, sizeof(c));19         for(i = 0; i < n; i++)20         for(j = 0; j < n; j++)21         {22             scanf("%d", &a[i][j]);23             a[i][j] %= 3;24         }25         for(i = 0; i < n; i++)26         for(j = 0; j < n; j++)27         {28             scanf("%d", &b[i][j]);29             b[i][j] %= 3;30         }31 32         for(i = 0; i < n; i++)33         {34             for(k = 0; k < n; k++)35             if(a[i][k]!=0)36             for(j = 0; j < n; j++)37             {38                c[i][j] += a[i][k]*b[k][j];39                //c[i][j] %= 3;  加这个会超时40             }41         }42         for(i = 0; i < n; i++)43         {44             for(j = 0; j < n; j++)45             if(j == 0)46             printf("%d", c[i][j]%3);47             else48             printf(" %d", c[i][j]%3);49             printf("\n");50         }51     }52     return 0;53 }

 

再贴一个崔老师的代码：

他把所有的0都忽略了，很巧妙的优化，aa[][], bb[][]里存储的是下一个不为0的位置：

 1 #include <iostream> 2 #include<stdio.h> 3 #include<vector> 4 #include<queue> 5 #include<stack> 6 #include<string.h> 7 #include<algorithm> 8 #include<map> 9 using namespace std;10 #define LL long long11 #define gcd(a,b) (b==0?a:gcd(b,a%b))12 #define lcm(a,b) (a*b/gcd(a,b))13 //O（n）求素数，1-n的欧拉数14 #define N 10001015 //A^x = A^(x % Phi(C) + Phi(C)) (mod C)16 int a[880][880];17 int b[880][880];18 int aa[880][880];19 int bb[880][880];20 int c[880][880];21 int main()22 {23     int n;24     while(~scanf("%d",&n))25     {26         memset(a,0,sizeof(a));27         memset(b,0,sizeof(b));28         memset(aa,0,sizeof(aa));29         memset(bb,0,sizeof(bb));30         memset(c,0,sizeof(c));31         for(int i=1;i<=n;i++)32         {33             for(int j=1;j<=n;j++)34             {35                 scanf("%d",&a[i][j]);36                 a[i][j]%=3;37             }38         }39         for(int i=1;i<=n;i++)40         {41             for(int j=1;j<=n;j++)42             {43                 scanf("%d",&b[i][j]);44                 b[i][j]%=3;45             }46         }47         for(int i=1;i<=n;i++)48         {49             int x=-1;50             for(int j=n;j>=0;j--)51             {52                 aa[i][j]=x;53                 if(a[i][j])x=j;54             }55         }56         for(int i=1;i<=n;i++)57         {58             int x=-1;59             for(int j=n;j>=0;j--)60             {61                 bb[i][j]=x;62                 if(b[i][j])x=j;63             }64         }65         for(int i=1;i<=n;i++)66         {67             for(int j=aa[i][0];j!=-1;j=aa[i][j])68             {69                 for(int k=bb[j][0];k!=-1;k=bb[j][k])70                     c[i][k]+=a[i][j]*b[j][k];71             }72         }73         for(int i=1;i<=n;i++)74         {75             for(int j=1;j<=n;j++)76             {77                 printf("%d",c[i][j]%3);78                 if(j!=n)printf(" ");79                 else printf("\n");80             }81         }82     }83     return 0;84 }

 


联系
我们