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
题意 ：矩阵相乘
思路：复杂度O(n^3)是接受不了的，但是出于题目的意思%3，所以我们可以不去处理0的情况，我们把原本最里面的那层for（k ) 拿到最外面，然后当有一行的某列出现0 的时候，那么对应的所有列对应的行也就不加入计算了，再加上出入外挂水过
#include
#include
#include
#include
typedef long long ll; using namespace std; const int maxn = 805; int a[maxn][maxn], b[maxn][maxn], c[maxn][maxn]; int n; int Scan() { int res = 0, ch, flag = 0; if ((ch = getchar()) == '-') flag = 1; else if (ch >= '0' && ch <= '9') res = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') res = res * 10 + ch - '0'; return flag?-res:res; } int main() { while (scanf("%d", &n) != EOF) { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { a[i][j] = Scan() % 3; c[i][j] = 0; } for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) b[i][j] = Scan() % 3; for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) if (a[i][k]) for (int j = 1; j <= n; j++) c[i][j] += a[i][k] * b[k][j]; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) printf("%d%c", c[i][j]%3, (j==n)?'\n':' '); } return 0; }