POJ 3318 Matrix Multiplication

Description

You are given three n × n matrices A, B and C. Does the equation A × B = C hold true?

Input

The first line of input contains a positive integer n (n ≤ 500) followed by the the three matrices A, B and C respectively. Each matrix’s description is a block of n × n integers.

It guarantees that the elements of A and B are less than 100 in absolute value and elements of C are less than 10,000,000 in absolute value.

Output

Output “YES” if the equation holds true, otherwise “NO”.

Sample Input

2
1 0
2 3
5 1
0 8
5 1
10 26

Sample Output

YES

Hint

Multiple inputs will be tested. So O(n3) algorithm will get TLE.

Solution

如果\(A*B=C\)那么\(A*B*X=C*X\),反之如果\(A*B*X=C*X\),那么我们有很大的几率说\(A*B=C\)。因此我们随机生成几个\(X\)检验即可。

Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1<<30;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
LL A[505][505], B[505][505], C[505][505], X[505], T[505], TT[505], TTT[505];
int n;
void read() {
	n=getint();
	for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) A[i][j]=getint();
	for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) B[i][j]=getint();
	for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) C[i][j]=getint();
}
int main() {
	read();
	for (int ii = 0; ii < 10; ++ii) {
		for (int i = 1; i <= n; ++i) {
			X[i] = rand() * rand();
			T[i] = 0; TT[i] = 0; TTT[i] = 0;
		}
		for (int i = 1; i <= n; ++i)
			for (int k = 1; k <= n; ++k)
				T[i] += B[i][k] * X[k];
		for (int i = 1; i <= n; ++i)
			for (int k = 1; k <= n; ++k)
				TT[i] += A[i][k] * T[k];
		for (int i = 1; i <= n; ++i)
			for (int k = 1; k <= n; ++k)
				TTT[i] += C[i][k] * X[k];
		for (int i = 1; i <= n; ++i) if (TT[i] != TTT[i]) {
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
	return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据