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

提出ソース

結果

問題	No.2272 多項式乗算 mod 258280327
ユーザー	👑 p-adic
提出日時	2022-09-28 15:26:46
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE (最新) AC (最初)
実行時間	-
コード長	5,365 bytes
コンパイル時間	567 ms
コンパイル使用メモリ	71,136 KB
実行使用メモリ	9,124 KB
最終ジャッジ日時	2023-09-16 11:50:26
合計ジャッジ時間	4,243 ms
ジャッジサーバーID （参考情報）	judge11 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	22 ms 8,844 KB
testcase_01	AC	22 ms 8,904 KB
testcase_02	AC	23 ms 8,904 KB
testcase_03	AC	22 ms 8,872 KB
testcase_04	AC	23 ms 9,004 KB
testcase_05	AC	23 ms 9,012 KB
testcase_06	AC	22 ms 8,964 KB
testcase_07	AC	23 ms 8,896 KB
testcase_08	AC	23 ms 8,908 KB
testcase_09	AC	22 ms 8,908 KB
testcase_10	AC	4 ms 9,052 KB
testcase_11	AC	4 ms 8,904 KB
testcase_12	AC	4 ms 8,836 KB
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	AC	23 ms 8,960 KB
testcase_19	AC	22 ms 8,964 KB
testcase_20	AC	24 ms 8,904 KB
testcase_21	AC	22 ms 9,056 KB
testcase_22	AC	25 ms 8,884 KB
testcase_23	AC	24 ms 8,856 KB
testcase_24	AC	23 ms 8,852 KB
testcase_25	AC	27 ms 8,840 KB
testcase_26	AC	27 ms 8,948 KB
testcase_27	AC	32 ms 8,916 KB
testcase_28	AC	32 ms 9,124 KB
testcase_29	RE	-
testcase_30	RE	-
testcase_31	RE	-
testcase_32	RE	-

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

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード