BZOJ-2396: 神奇的矩阵（随机判定）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2396

神奇的方法，随机出一个1n的矩阵D，然后通过比较DC和DAB来判定，多跑几次就可以A了。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

 

using namespace std ;

 

#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

#define check( ch ) ( ch >= '0' && ch <= '9' )

 

inline void getint( int &t ) {

    int ch ; for ( ch = getchar(  ) ; ! check( ch ) ; ch = getchar(  ) ) ;

    t = ch - '0' ;

    for ( ch = getchar(  ) ; check( ch ) ; ch = getchar(  ) ) t = t * 10 + ch - '0' ;

}

 

const int maxn = 1010 ;

 

int n , A[ maxn ][ maxn ] , B[ maxn ][ maxn ] , C[ maxn ][ maxn ] , D[ maxn ] , E[ maxn ] , F[ maxn ] ;

 

inline void mul( int a[] , int b[ maxn ][ maxn ] , int c[] ) {

    rep( i , n ) c[ i ] = 0 ;

    rep( i , n ) rep( j , n ) c[ i ] += a[ j ] * b[ j ][ i ] ;

}

 

inline bool cmp( int a[] , int b[] ) {

    rep( i , n ) if ( a[ i ] != b[ i ] ) return false ;

    return true ;

}

 

int main(  ) {

    srand( 12 ) ;

    while ( scanf( "%d" , &n ) != EOF ) {

        rep( i , n ) rep( j , n ) getint( A[ i ][ j ] ) ;

        rep( i , n ) rep( j , n ) getint( B[ i ][ j ] ) ;

        rep( i , n ) rep( j , n ) getint( C[ i ][ j ] ) ;

        bool flag = true ;

        rep( i , 11 ) {

            rep( j , n ) D[ j ] = rand(  ) % 10007 ;

            mul( D , A , F ) ; mul( F , B , E ) ; mul( D , C , F ) ;

            if ( ! cmp( E , F ) ) {

                flag = false ; break ;

            }

        }

        printf( flag ? "Yes\n" : "No\n" ) ;

    }

    return 0 ;

}