矩阵乘法 --- hdu 4920 ： Matrix multiplication

时间：2022-02-13 10:50:24

Matrix multiplication

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 820    Accepted Submission(s): 328

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
Author
Xiaoxu Guo (ftiasch)
Source

Mean:

给你两个矩阵，计算两个矩阵的积。

nalyse:

很多人认为这题用暴力过不了，时间复杂度为O(n^3),800^3=512000000，差不多要接近于10^9了，可能是hdu的评测速度给力吧，再加上这题是单点评测，每个评测点的时限都有2000ms，所以说暴力过了也实属正常。

Time complexity：O(n^3)

Source code：

#include<stdio.h>

int a[800][800],b[800][800],c[800][800],n,i,j,k;

int main(){

    while(scanf("%d",&n)!=EOF){

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

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

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

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

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

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

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

            for(j=0;j<i;++j)

                k=b[i][j],b[i][j]=b[j][i],b[j][i]=k;

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

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

                c[i][j]=0;

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

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

                c[i][j]%=3;

            }

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

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

                printf(j==n-1?"%d\n":"%d ",c[i][j]);

    }

    return 0;

}

　　

相关文章