#pragma GCC optimize ( "O3" ) #pragma GCC target ( "avx" ) #include #include #include #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 int main() { UNTIE; CEXPR( int , N , 19 ); bool M[N][N] = {}; int Aij_min; FOR( i , 0 , N ){ CIN_ASSERT( Li , 0 , N ); bool ( &Mi )[N] = M[i]; Aij_min = 1; FOR( j , 0 , Li ){ CIN_ASSERT( Aij , Aij_min , N ); Mi[Aij - 1] = true; Aij_min = Aij + 1; } } vector > S[N+1]{}; vector S_int[N+1]{}; CEXPR( int , PN , 1 << 19 ); int s_copy , size; FOR( s , 0 , PN ){ s_copy = s; vector I{}; FOR( i , 0 , N ){ if( s_copy % 2 == 1 ){ I.push_back( i ); } s_copy /= 2; if( s_copy == 0 ){ break; } } size = I.size(); S[size].push_back( move( I ) ); S_int[size].push_back( s ); } map det[N+1][2] = {}; { map ( &det0 )[2] = det[0]; det0[0][0] = 1; det0[1][0] = 0; } int i_r , I_j , s , s_sub; FOREQ( c , 1 , N ){ vector >& Sc = S[c]; vector& Sc_int = S_int[c]; map ( &det_c )[2] = det[c]; map ( &det_c_prev )[2] = det[c-1]; map& det_c0 = det_c[0]; map& det_c1 = det_c[1]; size = Sc.size(); FOR( k , 0 , size ){ vector& I = Sc[k]; s = Sc_int[k]; ll& det_c0s = ( det_c0[s] = 0 ); ll& det_c1s = ( det_c1[s] = 0 ); bool ( &Mi )[N] = M[N - c]; FOR( j , 0 , c ){ I_j = I[j]; if( Mi[I_j] ){ s_sub = s - ( 1 << I_j ); i_r = j % 2; det_c0s += det_c_prev[i_r][s_sub]; det_c1s += det_c_prev[1-i_r][s_sub]; } } } } map ( &det_N )[2] = det[N]; ll& det_N0 = det_N[0][PN-1]; ll& det_N1 = det_N[1][PN-1]; cout << det_N0 << " " << det_N1 << "\n"; QUIT; }