結果

問題 No.2272 多項式乗算 mod 258280327
コンテスト
ユーザー 👑 p-adic
提出日時 2023-04-09 16:12:29
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 160 ms / 2,000 ms
コード長 5,912 bytes
コンパイル時間 1,232 ms
コンパイル使用メモリ 81,708 KB
最終ジャッジ日時 2025-02-12 04:14:46
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ( "O3" )
#pragma GCC optimize( "unroll-loops" )
#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#include <iostream>
#include <stdio.h>
#include <stdint.h>
#include <cassert>
using namespace std;

using ll = long long;

#define MAIN main
#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define CEXPR( LL , BOUND , VALUE ) constexpr 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 COUT( ANSWER ) cout << ( ANSWER ) << "\n";
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT

int MAIN()
{
  UNTIE;
  CEXPR( int , power3_max , 531441 ); // 400000を超える最小の3羃3^12
  CEXPR( int , bound_deg , 200000 );
  CEXPR( ll , bound_coef , 1000000000000000000 );
  CEXPR( ll , P , 258280327 );
  CIN_ASSERT( deg_F , 0 , bound_deg );
  ll F[2][power3_max] = {};
  ll ( &F0 )[power3_max] = F[0];
  FOREQ( i , 0 , deg_F ){
    CIN_ASSERT( F_i , 0 , bound_coef );
    F0[i] = move( F_i );
  }
  CIN_ASSERT( deg_G , 0 , bound_deg );
  ll G[2][power3_max] = {};
  ll ( &G0 )[power3_max] = G[0];
  FOREQ( i , 0 , deg_G ){
    CIN_ASSERT( G_i , 0 , bound_coef );
    G0[i] = move( G_i );
  }
  assert( deg_F > 0 ? F0[deg_F] > 0 : true );
  assert( deg_G > 0 ? G0[deg_G] > 0 : true );
  if( deg_F == 0 ){
    if( F0[0] == 0 ){
      COUT( 0 );
      RETURN( 0 );
    }
  }
  if( deg_G == 0 ){
    if( G0[0] == 0 ){
      COUT( 0 );
      RETURN( 0 );
    }
  }
  FOREQ( i , 0 , deg_F ){
    F0[i] %= P;
  }
  FOREQ( i , 0 , deg_G ){
    G0[i] %= P;
  }
  int deg_FG = deg_F + deg_G;
  COUT( deg_FG );
  while( F0[deg_F] == 0 && deg_F > 0 ){
    deg_F--;
  }
  while( G0[deg_G] == 0 && deg_G > 0 ){
    deg_G--;
  }
  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;
  CEXPR( 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;
  CEXPR( int , exponent_max , 12 ); // log_3 power3_max
  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 );
  }
  CEXPR( ll , power3_max_inv , 258279841 );
  ll ( &F_prev )[power3_max] = F[index_prev];
  FOR( i , 0 , deg_FG ){
    cout << ( F_prev[i] * power3_max_inv ) % P << " ";
  }
  RETURN( ( F_prev[deg_FG] * power3_max_inv ) % P );
}
0