首页 > 代码库 > POJ 3318 Matrix Multiplication(随机化算法)
POJ 3318 Matrix Multiplication(随机化算法)
给你三个矩阵A,B,C。让你判断A*B是否等于C。
随机一组数据,然后判断乘以A,B之后是否与乘C之后相等。
很扯淡的啊,感觉这种算法不严谨啊、、、
Matrix Multiplication
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 16255 | Accepted: 3515 |
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.
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <time.h> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #define max( x, y ) ( ((x) > (y)) ? (x) : (y) ) #define min( x, y ) ( ((x) < (y)) ? (x) : (y) ) #define Mod 1000000007 #define LL long long using namespace std; const int maxn = 510; int a[maxn][maxn]; int b[maxn][maxn]; int c[maxn][maxn]; int f[maxn]; int aa[maxn]; int bb[maxn]; int cc[maxn]; int main() { int n; cin >>n; memset(aa, 0, sizeof(aa)); memset(bb, 0, sizeof(bb)); memset(cc, 0, sizeof(cc)); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) scanf("%d",&a[i][j]); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) scanf("%d",&b[i][j]); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) scanf("%d",&c[i][j]); srand((unsigned int)time(0)); for(int i = 0; i < n; i++) f[i] = rand()%100; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { bb[i] += b[i][j]*f[j]; cc[i] += c[i][j]*f[j]; } } for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) aa[i] += a[i][j]*bb[j]; int flag = 0; for(int i = 0; i < n; i++) { if(aa[i] != cc[i]) { flag = 1; break; } } if(flag) cout<<"NO"<<endl; else cout<<"YES"<<endl; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。