各种TEL，233啊。没想到是处理掉0的情况就能够过啊。一直以为会有极端数据。没想到居然是这种啊、、在网上看到了一个AC的奇妙的代码，经典的矩阵乘法，仅仅只是把最内层的枚举，移到外面就过了啊、、、有点不理解啊，复杂度不是一样的吗、、
Matrix multiplication
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 640 Accepted Submission(s): 250
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.
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).
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.
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
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-12
///#define M 1000100
#define LL __int64
///#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)<eps)? 0:x) using namespace std; const int maxn = 810; int a[maxn][maxn];
int b[maxn][maxn];
int c[maxn][maxn];
int aa[maxn][maxn];
int bb[maxn][maxn]; int main()
{
int n;
while(cin >>n)
{
memset(c, 0, sizeof(c));
memset(aa, 0, sizeof(aa));
memset(bb, 0, sizeof(bb));
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;
}
}
for(int i = 1; i <= n; i++)
{
int x = -1;
for(int j = n; j >= 0; j--)
{
aa[i][j] = x;
if(a[i][j]) x = j;
}
} for(int i = 1; i <= n; i++)
{
int x = -1;
for(int j = n; j >= 0; j--)
{
bb[i][j] = x;
if(b[i][j]) x = j;
}
}
for (int i = 1; i <= n; i++)
{
for(int j = aa[i][0]; j != -1; j = aa[i][j])
{
for(int k = bb[j][0]; k != -1; k = bb[j][k])
c[i][k] += a[i][j]*b[j][k];
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n-1; j++)
printf("%d ",c[i][j]%3);
printf("%d\n",c[i][n]%3);
}
}
return 0;
}
这是看到有人交的AC的代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 805;
int a[N][N], b[N][N], ans[N][N];
int main()
{
int n, i, j, k;
while(~scanf("%d",&n))
{
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
scanf("%d",&a[i][j]);
a[i][j] %= 3;
}
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
scanf("%d",&b[i][j]);
b[i][j] %= 3;
}
memset(ans, 0, sizeof(ans));
for(k = 1; k <= n; k++) //经典算法中这层循环在最内层。放最内层会超时，可是放在最外层或者中间都不会超时，不知道为什么
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
ans[i][j] += a[i][k] * b[k][j];
//ans[i][j] %= 3; //假设在这里对3取余，就超时了
}
for(i = 1; i <= n; i++)
{
for(j = 1; j < n; j++)
printf("%d ", ans[i][j] % 3);
printf("%d\n", ans[i][n] % 3);
}
}
return 0;
}