POJ 3318 - Matrix Multiplication 第一次用隨機化解決問題...

 隨機化還是很厲害的...印象最深的是以前手寫快排~~一般加個隨機化會使耗時不受輸入數據的..時間更加穩定

     這個題是人品題了...開始交了好多遍都過不了..多交幾次終於過了...

Program:

 #include<iostream>   
#include<stack>   
#include<queue>   
#include<stdio.h>   
#include<algorithm>   
#include<string.h>   
#include<time.h>   
#include<cmath>   
#define ll long long   
#define oo 1000000007   
#define MAXN 505   
using namespace std;   
int n,M[3][MAXN][MAXN];  
bool judge()  
{  
      int t,i,j,x,y,p,d;   
      for (t=1;t<=60000;t++)  
      {   
             y=rand()%n;  
             x=rand()%n;  
             d=0;  
             for (p=0;p<n;p++)  
                d+=M[0][y][p]*M[1][p][x];  
             if (d!=M[2][y][x]) return false;  
      }  
      return true;  
}   
int main()  
{  
      int i,j,x;   
      scanf("%d",&n);  
      for (x=0;x<3;x++)  
         for (i=0;i<n;i++)  
           for (j=0;j<n;j++)  
              scanf("%d",&M[x][i][j]);  
      srand((unsigned)time(NULL));  
      if (judge()) printf("YES\n");  
             else  printf("NO\n");  
      return 0;  
}