【HDU】4920 - Matrix multiplication（矩阵相乘）

点击打开题目

Matrix multiplication

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

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 A ij. The next n lines describe the matrix B in similar format (0≤A ij,B ij≤10 9).

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

考的矩阵相乘，行列都是n直接乘就行了。

用G++提交，C++会TLE的。（这个代码可能还能优化）

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define MOD 3
int A[808][808],B[808][808],C[808][808];
int main()
{
	int n;
	while (~scanf ("%d",&n))
	{
		for (int i = 1 ; i <= n ; i++)
		{
			for (int j = 1 ; j <= n ; j++)
			{
				scanf ("%d",&A[i][j]);
				A[i][j] %= 3;
			}
		}
		for (int i = 1 ; i <= n ; i++)
		{
			for (int j = 1 ; j <= n ; j++)
			{
				scanf ("%d",&B[i][j]);
				B[i][j] %= 3;
			}
		}
		CLR(C,0);
		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] = (C[i][k] + A[i][j] * B[j][k]) % MOD;
			}
		}
		for (int i = 1 ; i <= n ; i++)
		{
			for (int j = 1 ; j < n ; j++)
				printf ("%d ",C[i][j]);
			printf ("%d\n",C[i][n]);
		}
	}
	return 0;
}