// 中国剰余定理による解法 #include #include #include #include using namespace std; using ll = long long; #define TYPE_OF( VAR ) remove_const::type >::type #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE #define CIN( LL , A ) LL A; cin >> A #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) ) #define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define QUIT return 0 #define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT #define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \ ll ANSWER{ 1 }; \ { \ ll ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ( ARGUMENT ) % MODULO ) ) % MODULO; \ TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \ while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \ if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \ ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \ } \ ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \ EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \ } \ } \ inline CEXPR( int , bound_size , 15 ); inline CEXPR( int , bound_r , 9 ); int Rank( const ll ( &A )[bound_size][bound_size] , const int& L , const int& M ) { constexpr ll P[bound_r] = {10000019,10000079,10000103,10000121,10000139,10000141,10000169,10000189,10000223}; int rank = 0; FOR( r , 0 , bound_r ){ const ll& P_r = P[r]; ll A_copy[bound_size][bound_size]; FOR( i , 0 , L ){ const ll ( &A_i )[bound_size] = A[i]; ll ( &A_copy_i )[bound_size] = A_copy[i]; FOR( j , 0 , M ){ A_copy_i[j] = A_i[j]; } } int i_min = 0; int i_curr; int j_curr = 0; while( i_min < L && j_curr < M ){ i_curr = i_min; while( i_curr < L ? A_copy[i_curr][j_curr] % P_r == 0 : false ){ i_curr++; } if( i_curr < L ){ swap( A_copy[i_min] , A_copy[i_curr] ); ll ( &A_copy_i_min )[bound_size] = A_copy[i_min]; POWER_MOD( inv , A_copy_i_min[j_curr] , P_r - 2 , P_r ); FOR( j , j_curr , M ){ ( A_copy_i_min[j] *= inv ) %= P_r; } FOR( i , i_min + 1 , L ){ ll ( &A_copy_i )[bound_size] = A_copy[i]; ll A_copy_i_j_curr = A_copy_i[j_curr]; FOR( j , j_curr , M ){ ll& A_copy_ij = A_copy_i[j] -= A_copy_i_j_curr * A_copy_i_min[j]; } } i_min++; } j_curr++; } rank < i_min ? rank = i_min : rank; } return rank; } int main() { UNTIE; CIN_ASSERT( L , 1 , bound_size ); CIN_ASSERT( M , 1 , bound_size / L ); CIN_ASSERT( N , 1 , bound_size / M ); CEXPR( ll , bound , 6 ); ll A[bound_size][bound_size]; FOR( i , 0 , L ){ ll ( &Ai )[bound_size] = A[i]; FOR( j , 0 , M ){ CIN_ASSERT( Aij , - bound , bound ); Ai[j] = Aij; } } ll B[bound_size][bound_size]; FOR( j , 0 , M ){ ll ( &Bj )[bound_size] = B[j]; FOR( k , 0 , N ){ CIN_ASSERT( Bjk , - bound , bound ); Bj[k] = Bjk; } } ll sum = 0; FOR( i , 0 , L ){ ll ( &Ai )[bound_size] = A[i]; FOR( k , 0 , N ){ FOR( j , 0 , M ){ sum += Ai[j] * B[j][k]; } if( sum != 0 ){ RETURN( "No" ); } } } int rankA = Rank( A , L , M ); int rankB = Rank( B , M , N ); RETURN( rankB == M - rankA ? "Yes" : "No" ); }