首页 > 代码库 > hdu 4920 Matrix multiplication（矩阵乘法）

hdu 4920 Matrix multiplication（矩阵乘法）

2024-07-15 23:52:46   220人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4920


Matrix multiplication

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

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
2014 Multi-University Training Contest 5
 
Recommend
We have carefully selected several similar problems for you:  4919 4918 4917 4916 4915 

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 801;
const int mod = 3;
int A[MAXN][MAXN], B[MAXN][MAXN];
int C[MAXN][MAXN];
int n;

void input()
{
    int i, j;
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
        {
            scanf("%d",&A[i][j]);
            A[i][j] %= mod;
        }
    }
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
        {
            scanf("%d",&B[i][j]);
            B[i][j] %= mod;
        }
    }
}

void multi()
{//两个相等矩阵的乘法，对于稀疏矩阵，有在0处不用运算的优化
    memset(C,0,sizeof(C));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(A[i][j] == 0)//稀疏矩阵优化
                continue;
            for(int k = 1; k <= n; k++)
            {
                C[i][k] += A[i][j]*B[j][k];//i行k列第j项
            //    C[i][k] %= mod;
            }
        }
    }
}

void print()//输出矩阵信息
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(j == 1)
                printf("%d",C[i][j]%mod);
            else
                printf(" %d",C[i][j]%mod);
        }
        printf("\n");
    }
}

int main()
{
    while(~scanf("%d",&n))
    {
        input();
        multi();
        print();
    }
    return 0;
}

加输入外挂代码如下：（要快上一些）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 817;
const int mod = 3;
int A[MAXN][MAXN], B[MAXN][MAXN];
int C[MAXN][MAXN];
int n;

int Scan()
{
	int res = 0, ch;
	ch=getchar();
	if(ch >= '0' && ch <= '9')		 
		res = ch - '0';
	while((ch = getchar()) >= '0' && ch <= '9' )
		res = res * 10 + ch - '0';
	return res;
}

void input()
{
	int i, j;
	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= n; j++)
		{
			//scanf("%d",&A[i][j]);
			//A[i][j] %= mod;
			A[i][j]=Scan()%3;
		}
	}
	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= n; j++)
		{
			//scanf("%d",&B[i][j]);
			//B[i][j] %= mod;
			B[i][j]=Scan()%3;
		}
	}
}

void multi()
{//两个相等矩阵的乘法，对于稀疏矩阵，有在0处不用运算的优化
	memset(C,0,sizeof(C));
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			if(A[i][j] == 0)//稀疏矩阵优化
				continue;
			for(int k = 1; k <= n; k++)
			{
				C[i][k] += A[i][j]*B[j][k];//i行k列第j项
			//	C[i][k] %= mod;
			}
		}
	}
}

void print()//输出矩阵信息
{
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			if(j == 1)
				printf("%d",C[i][j]%mod);
			else
				printf(" %d",C[i][j]%mod);
		}
		printf("\n");
	}
}

int main()
{
	while(~scanf("%d",&n))
	{
		input();
		multi();
		print();
	}
	return 0;
}


联系
我们