HDU 4920 Matrix multiplication

题目链接：HDU 4920

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

题意

输入两个矩阵，然后输出他们的乘积得出的矩阵，并且模3.

题解：

暴力就可以了，刚开始想复杂了，然后写了个类，重载了*号，然后果断超时了，上网查了一下，说是什么在乘的时候有个优化处理，类似这样：

for (int i(0); i<n; i++)
			for (int j(0); j < n; j++) {
				for (int k(0); k < n; k++) {
					F3[i][k] += (F1[i][j] * F2[j][k]);
				}
			}

但是我发现不用这个优化也过了，而且就差了几十ms，所以还是个暴力题。。。

for (int i(0); i<n; i++)
			for (int j(0); j < n; j++) {
				for (int k(0); k < n; k++) {
					F3[i][j] += (F1[i][k] * F2[k][j]);
				}
			}

代码

#include<cstdio>
#include<string.h>
using namespace std;
int F1[800][800], F2[800][800],F3[800][800];
int main() {
	int n,t;
	while (scanf("%d",&n)!=EOF) {
		memset(F3, 0, sizeof F3);
		//a.m_n = n;
		//b.m_n = n;
		for (int i(0); i < n; i++)
			for (int j(0); j < n; j++) {
				//cin >>t;
				scanf("%d", &t);
				F1[i][j] = t % 3;
			}
		for (int i(0); i < n; i++)
			for (int j(0); j < n; j++) {
				//cin >> t;
				scanf("%d", &t);
				F2[i][j] = t % 3;
			}
		for (int i(0); i<n; i++)
			for (int j(0); j < n; j++) {
				for (int k(0); k < n; k++) {
					F3[i][j] += (F1[i][k] * F2[k][j]);
				}
			}
		for (int i(0); i < n; i++) {
			for (int j(0); j < n; j++) {
				if (j)printf(" ");
				printf("%d", F3[i][j] % 3);
				//cout << F3[i][j]%3;
			}
			//cout << endl;
			printf("
");
		}
		//Print(a*b);
	}
	return 0;
}