結果

問題 No.2272 多項式乗算 mod 258280327
ユーザー 👑 p-adic
提出日時 2022-09-28 15:26:46
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,365 bytes
コンパイル時間 1,035 ms
コンパイル使用メモリ 70,440 KB
最終ジャッジ日時 2025-02-07 17:52:48
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24 RE * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <string>
#include <stdio.h>
#include <stdint.h>
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<remove_reference<decltype( FINAL_PLUS_ONE )>::type >::type VAR = INITIAL ; VAR < 
    FINAL_PLUS_ONE ; VAR ++ ) 
#define FOREQ( VAR , INITIAL , FINAL ) for( remove_const<remove_reference<decltype( FINAL )>::type >::type VAR = INITIAL ; VAR <= FINAL ; VAR ++ )  
#define QUIT return 0 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT 
#include <cassert>
#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0