You are given three n × n matrices A, B and C. Does the equation A × B = C hold true?
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 "YES" if the equation holds true, otherwise "NO".
2 1 0 2 3 5 1 0 8 5 1 10 26Sample Output
YESHint
Multiple inputs will be tested. So O(n
3) algorithm will get TLE.
#include<iostream>
#include<ctime>
using namespace std;
const int maxn = 505;
int A[maxn][maxn];
int B[maxn][maxn];
int C[maxn][maxn];
int main()
{int N;while(cin >> N){bool flag=true;for (int i = 1; i <=N; i++)for (int j = 1; j <=N; j++){scanf("%d",&A[i][j]);}for (int i = 1; i <=N; i++)for (int j = 1; j <=N; j++){scanf("%d",&B[i][j]);}for (int i = 1; i <=N; i++)for (int j = 1; j <=N; j++){scanf("%d",&C[i][j]);}srand((unsigned)time(NULL));for (int i = 0; i< 77777;i++){int h = rand()%N + 1,l = rand()%N + 1;int temp = 0;for (int j = 1;j <=N;j++){temp += A[h][j] * B[j][l] ;}if(temp != C[h][l]){flag = false;break;}}if(flag){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}}