设为首页 加入收藏

TOP

POJ 3318 Matrix Multiplication(随机化算法)
2015-07-20 17:59:37 来源: 作者: 【大 中 小】 浏览:1次
Tags：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(n 3) algorithm will get TLE. 
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               #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"<
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：Leetcode--Divide Two Integers 下一篇：ural 1932 The Secret of Identif..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: