hdu 4920 Matrix multiplication （矩阵计算）

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

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

 #include <iostream>

 #include <cstdio>

 #include <vector>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 const int maxn = +;

 using namespace std;

 int n, a[maxn][maxn], b[maxn][maxn], c[maxn][maxn];

 int main()

 {

     int i, j, k;

     while(~scanf("%d", &n))

     {

         memset(a, , sizeof(a));

         memset(b, , sizeof(b));

         memset(c, , sizeof(c));

         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++)

         {

             for(k = ; k < n; k++)

             if(a[i][k]!=)

             for(j = ; j < n; j++)

             {

                c[i][j] += a[i][k]*b[k][j];

                //c[i][j] %= 3;  加这个会超时

             }

         }

         for(i = ; i < n; i++)

         {

             for(j = ; j < n; j++)

             if(j == )

             printf("%d", c[i][j]%);

             else

             printf(" %d", c[i][j]%);

             printf("\n");

         }

     }

     return ;

 }

再贴一个崔老师的代码：

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

 #include <iostream>

 #include<stdio.h>

 #include<vector>

 #include<queue>

 #include<stack>

 #include<string.h>

 #include<algorithm>

 #include<map>

 using namespace std;

 #define LL long long

 #define gcd(a,b) (b==0?a:gcd(b,a%b))

 #define lcm(a,b) (a*b/gcd(a,b))

 //O（n）求素数，1-n的欧拉数

 #define N 100010

 //A^x = A^(x % Phi(C) + Phi(C)) (mod C)

 int a[][];

 int b[][];

 int aa[][];

 int bb[][];

 int c[][];

 int main()

 {

     int n;

     while(~scanf("%d",&n))

     {

         memset(a,,sizeof(a));

         memset(b,,sizeof(b));

         memset(aa,,sizeof(aa));

         memset(bb,,sizeof(bb));

         memset(c,,sizeof(c));

         for(int i=;i<=n;i++)

         {

             for(int j=;j<=n;j++)

             {

                 scanf("%d",&a[i][j]);

                 a[i][j]%=;

             }

         }

         for(int i=;i<=n;i++)

         {

             for(int j=;j<=n;j++)

             {

                 scanf("%d",&b[i][j]);

                 b[i][j]%=;

             }

         }

         for(int i=;i<=n;i++)

         {

             int x=-;

             for(int j=n;j>=;j--)

             {

                 aa[i][j]=x;

                 if(a[i][j])x=j;

             }

         }

         for(int i=;i<=n;i++)

         {

             int x=-;

             for(int j=n;j>=;j--)

             {

                 bb[i][j]=x;

                 if(b[i][j])x=j;

             }

         }

         for(int i=;i<=n;i++)

         {

             for(int j=aa[i][];j!=-;j=aa[i][j])

             {

                 for(int k=bb[j][];k!=-;k=bb[j][k])

                     c[i][k]+=a[i][j]*b[j][k];

             }

         }

         for(int i=;i<=n;i++)

         {

             for(int j=;j<=n;j++)

             {

                 printf("%d",c[i][j]%);

                 if(j!=n)printf(" ");

                 else printf("\n");

             }

         }

     }

     return ;

 }

巴特西

hdu 4920 Matrix multiplication （矩阵计算）

最新文章

热门文章