// 確率的(mod 1000000007)解法 #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( ll , P , 998244353 ); inline CEXPR( ll , P , 1000000007 ); int Rank( ll ( &A )[bound_size][bound_size] , const int& L , const int& M ) { 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[i_curr][j_curr] == 0 : false ){ i_curr++; } if( i_curr < L ){ swap( A[i_min] , A[i_curr] ); ll ( &A_i_min )[bound_size] = A[i_min]; POWER_MOD( inv , A_i_min[j_curr] , P - 2 , P ); FOR( j , j_curr , M ){ ( A_i_min[j] *= inv ) %= P; } FOR( i , i_min + 1 , L ){ ll ( &A_i )[bound_size] = A[i]; ll A_i_j_curr = A_i[j_curr]; FOR( j , j_curr , M ){ ( A_i[j] -= A_i_j_curr * A_i_min[j] ) %= P; } } i_min++; } j_curr++; } return i_min; } 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 < 0 ? Aij += P : 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 < 0 ? Bjk += P : 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] ) %= P; } if( sum != 0 ){ RETURN( "No" ); } } } int rankA = Rank( A , L , M ); int rankB = Rank( B , M , N ); RETURN( rankB == M - rankA ? "Yes" : "No" ); }