#include #include #include #include using namespace std; using ll = long long; #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CIN( LL , A ) LL A; cin >> A #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( remove_const::type >::type VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOREQ( VAR , INITIAL , FINAL ) for( remove_const::type >::type VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define QUIT return 0 #define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT #include #define MAIN main int MAIN() { UNTIE; constexpr const int bound_D = 1 << 16; constexpr const ll bound_C = bound_D; constexpr const int power3_max = 177147; constexpr const int exponent_max = 11; constexpr const ll power3_max_inv = 258278869; CIN( int , D_F ); assert( 0 <= D_F && D_F <= bound_D ); ll F[2][power3_max] = {}; ll ( &F0 )[power3_max] = F[0]; ll C_i; FOREQ( i , 0 , D_F ){ cin >> C_i; assert( 0 <= C_i && C_i <= bound_C ); F0[i] = C_i; } CIN( int , D_G ); assert( 0 <= D_G && D_G <= bound_D ); ll G[2][power3_max] = {}; ll ( &G0 )[power3_max] = G[0]; FOREQ( i , 0 , D_G ){ cin >> C_i; assert( 0 <= C_i && C_i <= bound_C ); G0[i] = C_i; } if( D_F == 0 ){ if( F0[0] == 0 ){ cout << 0 << "\n"; cout << 0 << "\n"; QUIT; } } if( D_G == 0 ){ if( G0[0] == 0 ){ cout << 0 << "\n"; cout << 0 << "\n"; QUIT; } } constexpr const ll P = 258280327; constexpr const ll PRT[18] = { 1 , 216758952 , 101467526 , 192804416 , 176579501 , 103561696 , 231369983 , 149769107 , 226314423 , 92727751 , 62159786 , 188033136 , 81607097 , 60928536 , 166970816 , 33424748 , 1331 , 11 }; constexpr const ll IPRT[18] = { 1 , 41521374 , 172512859 , 90494136 , 146243611 , 250527318 , 145009132 , 221744278 , 147702524 , 152317402 , 95581115 , 192894340 , 201944950 , 228994089 , 118233014 , 114218248 , 37063518 , 93920119 }; int index_curr = 1; int index_prev = 0; ll PRT_e_power; constexpr const int power3_max_prev = power3_max / 3; int power3[2] = { power3_max , power3_max_prev }; int i_q_lim[2] = { 1 , 3 }; int i_q_r; FOREQ( exponent , 1 , exponent_max ){ ll ( &F_curr )[power3_max] = F[index_curr]; ll ( &G_curr )[power3_max] = G[index_curr]; int& power3_curr = power3[index_curr]; int& i_q_lim_curr = i_q_lim[index_curr]; ll ( &F_prev )[power3_max] = F[index_prev]; ll ( &G_prev )[power3_max] = G[index_prev]; int& power3_prev = power3[index_prev]; int& i_q_lim_prev = i_q_lim[index_prev]; const ll& PRT_e = PRT[exponent]; PRT_e_power = 1; FOR( i_q , 0 , i_q_lim_curr ){ i_q_r = i_q % i_q_lim_prev; FOR( i_r , 0 , power3_curr ){ F_curr[ i_q * power3_curr + i_r ] = ( F_prev[ i_q_r * power3_prev + i_r ] + PRT_e_power * F_prev[ i_q_r * power3_prev + power3_curr + i_r ] + ( ( PRT_e_power * PRT_e_power ) % P ) * F_prev[ i_q_r * power3_prev + power3_curr + power3_curr + i_r ] ) % P; G_curr[ i_q * power3_curr + i_r ] = ( G_prev[ i_q_r * power3_prev + i_r ] + PRT_e_power * G_prev[ i_q_r * power3_prev + power3_curr + i_r ] + ( ( PRT_e_power * PRT_e_power ) % P ) * G_prev[ i_q_r * power3_prev + power3_curr + power3_curr + i_r ] ) % P; } PRT_e_power = ( PRT_e_power * PRT_e ) % P; } power3_prev = power3_curr / 3; i_q_lim_prev = i_q_lim_curr * 3; swap( index_curr , index_prev ); } { ll ( &F_prev )[power3_max] = F[index_prev]; ll ( &G_prev )[power3_max] = G[index_prev]; FOR( i , 0 , power3_max ){ ll& F_prev_i = F_prev[i]; F_prev_i = ( F_prev_i * G_prev[i] ) % P; } } power3[index_curr] = power3_max_prev; power3[index_prev] = power3_max; i_q_lim[index_curr] = 3; i_q_lim[index_prev] = 1; FOREQ( exponent , 1 , exponent_max ){ ll ( &F_curr )[power3_max] = F[index_curr]; int& power3_curr = power3[index_curr]; int& i_q_lim_curr = i_q_lim[index_curr]; ll ( &F_prev )[power3_max] = F[index_prev]; int& power3_prev = power3[index_prev]; int& i_q_lim_prev = i_q_lim[index_prev]; const ll& IPRT_e = IPRT[exponent]; PRT_e_power = 1; FOR( i_q , 0 , i_q_lim_curr ){ i_q_r = i_q % i_q_lim_prev; FOR( i_r , 0 , power3_curr ){ F_curr[ i_q * power3_curr + i_r ] = ( F_prev[ i_q_r * power3_prev + i_r ] + PRT_e_power * F_prev[ i_q_r * power3_prev + power3_curr + i_r ] + ( ( PRT_e_power * PRT_e_power ) % P ) * F_prev[ i_q_r * power3_prev + power3_curr + power3_curr + i_r ] ) % P; } PRT_e_power = ( PRT_e_power * IPRT_e ) % P; } power3_prev = power3_curr / 3; i_q_lim_prev = i_q_lim_curr * 3; swap( index_curr , index_prev ); } int D_FG = D_F + D_G; cout << D_FG << "\n"; { ll ( &F_prev )[power3_max] = F[index_prev]; FOR( i , 0 , D_FG ){ cout << ( F_prev[i] * power3_max_inv ) % P << " "; } cout << ( F_prev[D_FG] * power3_max_inv ) % P << "\n"; } QUIT; }