#836801 (C++17) No.2272 多項式乗算 mod 258280327

提出ソース

結果

問題	No.2272 多項式乗算 mod 258280327
ユーザー	👑 p-adic
提出日時	2023-02-03 20:48:40
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA (最新) AC (最初)
実行時間	-
コード長	5,725 bytes
コンパイル時間	557 ms
コンパイル使用メモリ	71,932 KB
実行使用メモリ	20,312 KB
最終ジャッジ日時	2023-09-16 11:50:38
合計ジャッジ時間	4,884 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	66 ms 19,972 KB
testcase_01	AC	67 ms 19,916 KB
testcase_02	AC	67 ms 20,012 KB
testcase_03	AC	66 ms 19,984 KB
testcase_04	AC	67 ms 20,096 KB
testcase_05	AC	66 ms 19,920 KB
testcase_06	AC	66 ms 19,924 KB
testcase_07	AC	66 ms 19,900 KB
testcase_08	AC	66 ms 20,240 KB
testcase_09	AC	65 ms 20,200 KB
testcase_10	AC	7 ms 19,984 KB
testcase_11	AC	7 ms 19,916 KB
testcase_12	AC	7 ms 20,036 KB
testcase_13	AC	7 ms 19,944 KB
testcase_14	AC	5 ms 20,120 KB
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	AC	66 ms 19,916 KB
testcase_19	AC	66 ms 19,980 KB
testcase_20	AC	66 ms 19,980 KB
testcase_21	AC	66 ms 20,048 KB
testcase_22	AC	66 ms 20,080 KB
testcase_23	AC	67 ms 20,040 KB
testcase_24	AC	66 ms 20,048 KB
testcase_25	AC	70 ms 20,132 KB
testcase_26	AC	70 ms 19,908 KB
testcase_27	AC	76 ms 20,016 KB
testcase_28	AC	76 ms 19,988 KB
testcase_29	AC	120 ms 19,988 KB
testcase_30	AC	173 ms 20,048 KB
testcase_31	AC	164 ms 20,048 KB
testcase_32	AC	174 ms 19,984 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <string>
#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
  ll F[2][power3_max] = {};
  CEXPR( int , bound_deg , 200000 );
  CEXPR( ll , bound_coef , 1000000000000000000 );
  CEXPR( ll , P , 258280327 );
  CIN_ASSERT( deg_F , 0 , bound_deg );
  ll ( &F0 )[power3_max] = F[0];
  FOREQ( i , 0 , deg_F ){
    CIN_ASSERT( F_i , 0 , bound_coef );
    F0[i] = move( F_i %= P );
  }
  while( F0[deg_F] == 0 && deg_F > 0 ){
    deg_F--;
  }
  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 %= P );
  }
  while( G0[deg_G] == 0 && deg_G > 0 ){
    deg_G--;
  }
  if( deg_F == 0 ){
    if( F0[0] == 0 ){
      cout << 0 << "\n";
      cout << 0 << "\n";
      QUIT;
    }
  }
  if( deg_G == 0 ){
    if( G0[0] == 0 ){
      cout << 0 << "\n";
      cout << 0 << "\n";
      QUIT;
    }
  }
  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;
  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 );
  }
  int deg_FG = deg_F + deg_G;
  cout << deg_FG << "\n";
  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 << " ";
    }
    cout << ( F_prev[deg_FG] * power3_max_inv ) % P << "\n";
  }
  QUIT;
}

yukicoder

結果

テストケース

ソースコード