結果

問題 No.3404 形式群法則
コンテスト
ユーザー 👑 p-adic
提出日時 2023-10-14 02:36:00
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.89.0)
結果
AC  
実行時間 259 ms / 2,000 ms
コード長 8,346 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 9,685 ms
コンパイル使用メモリ 243,236 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-10 23:30:31
合計ジャッジ時間 12,053 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define SIGNAL signal( SIGABRT , &AlertAbort );
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )
  #define ASSERT( A , MIN , MAX ) CERR( "ASSERTチェック： " , ( MIN ) , ( ( MIN ) <= A ? "<=" : ">" ) , A , ( A <= ( MAX ) ? "<=" : ">" ) , ( MAX ) ); assert( ( MIN ) <= A && A <= ( MAX ) )
  #define CERR( ... ) VariadicCout( cerr , __VA_ARGS__ ) << endl
  #define COUT( ... ) VariadicCout( cout << "出力： " , __VA_ARGS__ ) << endl
  #define CERR_A( A , N ) OUTPUT_ARRAY( cerr , A , N ) << endl
  #define COUT_A( A , N ) cout << "出力： "; OUTPUT_ARRAY( cout , A , N ) << endl
  #define CERR_ITR( A ) OUTPUT_ITR( cerr , A ) << endl
  #define COUT_ITR( A ) cout << "出力： "; OUTPUT_ITR( cout , A ) << endl
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize ( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define SIGNAL 
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
  #define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
  #define CERR( ... ) 
  #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << "\n"
  #define CERR_A( A , N ) 
  #define COUT_A( A , N ) OUTPUT_ARRAY( cout , A , N ) << "\n"
  #define CERR_ITR( A ) 
  #define COUT_ITR( A ) OUTPUT_ITR( cout , A ) << "\n"
#endif
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
#define REPEAT_MAIN( BOUND ) int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); SIGNAL; DEXPR( int , bound_test_case_num , BOUND , min( BOUND , 100 ) ); int test_case_num = 1; if constexpr( bound_test_case_num > 1 ){ SET_ASSERT( test_case_num , 1 , bound_test_case_num ); } REPEAT( test_case_num ){ if constexpr( bound_test_case_num > 1 ){ CERR( "testcase " , VARIABLE_FOR_REPEAT_test_case_num , ":" ); } Solve(); CERR( "" ); } }
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , ... ) LL __VA_ARGS__; VariadicCin( cin , __VA_ARGS__ )
#define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#define CIN_ASSERT( A , MIN , MAX ) TYPE_OF( MAX ) A; SET_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 REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT_ ## HOW_MANY_TIMES , 0 , HOW_MANY_TIMES )

// 入出力用
template <class Traits> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicCin( basic_istream<char,Traits>& is , Arg& arg , ARGS&... args ) { return VariadicCin( is >> arg , args... ); }
template <class Traits> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator ) { return is; }
template <class Traits , typename Arg , typename... ARGS> inline basic_istream<char,Traits>& VariadicGetline( basic_istream<char,Traits>& is , const char& separator , Arg& arg , ARGS&... args ) { return VariadicGetline( getline( is , arg , separator ) , separator , args... ); }
template <class Traits , typename Arg> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg& arg ) { return os << arg; }
template <class Traits , typename Arg1 , typename Arg2 , typename... ARGS> inline basic_ostream<char,Traits>& VariadicCout( basic_ostream<char,Traits>& os , const Arg1& arg1 , const Arg2& arg2 , const ARGS&... args ) { return VariadicCout( os << arg1 << " " , arg2 , args... ); }

// デバッグ用
#ifdef DEBUG
  inline void AlertAbort( int n ) { CERR( "abort関数が呼ばれました。assertマクロのメッセージが出力されていない場合はオーバーフローの有無を確認をしてください。" ); }
  void AutoCheck( bool& auto_checked );
#endif

#define FACTORIAL_MOD( ANSWER , ANSWER_INV , INVERSE , MAX_INDEX , CONSTEXPR_LENGTH , MODULO ) \
  ll ANSWER[CONSTEXPR_LENGTH];					\
  ll ANSWER_INV[CONSTEXPR_LENGTH];				\
  ll INVERSE[CONSTEXPR_LENGTH];					\
  {									\
    ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1;				\
    ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL;			\
    FOREQ( i , 1 , MAX_INDEX ){						\
      ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= ( MODULO ); \
    }									\
    ANSWER_INV[0] = ANSWER_INV[1] = INVERSE[1] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \
    FOREQ( i , 2 , MAX_INDEX ){						\
      ANSWER_INV[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= INVERSE[i] = ( MODULO ) - ( ( ( ( MODULO ) / i ) * INVERSE[ ( MODULO ) % i ] ) % ( MODULO ) ) ) %= ( MODULO ); \
    }									\
  }									\


vector<ll> Convolution( const vector<ll>& f , const vector<ll>& g , const uint& N , const ll& P )
{

  vector<ll> fg( N + 1 );
  uint g_deg = g.size();
  g_deg == 0 ? g_deg : g_deg -= 1;

  for( uint d = 0 ; d <= N ; d++ ){

    const uint i_max = min( d , g_deg );
    
    for( uint i = 0 ; i <= i_max ; i++ ){

      ( fg[d] += f[d-i] * g[i] ) %= P;

    }

  }

  return fg;

}

vector<ll> Inverse( const vector<ll>& f , const uint& N , const ll& P )
{

  uint power_minus = 0;
  vector<ll> f_inv( power_minus + 1 );
  // f[0] == 1の場合のみサポート。
  // そうでない場合は1の代わりにf[0]の逆元を代入。
  f_inv[0] = 1;

  while( power_minus < N ){

    power_minus = ( power_minus << 1 ) | 1;
    f_inv.resize( power_minus + 1 );
    vector<ll> temp = Convolution( f_inv , f , power_minus , P );
    ( temp[0] = ( P == 2 ? 0 : 2 ) - temp[0] ) < 0 ? temp[0] += P : 0;

    for( uint d = 1 ; d <= power_minus ; d++ ){

      temp[d] > 0 ? temp[d] = P - temp[d] : 0;

    }
    
    f_inv = Convolution( f_inv , temp , power_minus , P );

  }

  f_inv.resize( N + 1 );
  return f_inv;
  
}

vector<ll> Composite( const vector<ll>& f , const vector<ll>& g , const uint& N , const ll& P )
{

  if( N == 0 ){

    return f;

  }

  const uint H = sqrt( N );
  const uint K = N / H;
  vector<vector<ll> > g_power( K < 2 ? 2 : K );
  g_power[0] = vector<ll>( N + 1 );
  g_power[0][0] = 1;
  g_power[1] = g;
  
  for( uint k = 2 ; k < K ; k++ ){

    g_power[k] = Convolution( g_power[k-1] , g_power[1] , N , P );

  }

  vector<vector<ll> > g_power2( H + 1 );
  g_power2[0] = vector<ll>( N + 1 );
  g_power2[0][0] = 1;
  g_power2[1] = Convolution( g_power[K-1] , g_power[1] , N , P );

  for( uint h = 2 ; h <= H ; h++ ){

    g_power2[h] = Convolution( g_power2[h-1] , g_power2[1] , N , P );

  }

  uint k = 0;
  uint h = 0;
  uint n_max = N;
  vector<ll> fg( N + 1 );
  vector<ll> fg_h( N + 1 );

  for( uint d = 0 ; d <= N ; d++ ){

    for( uint n = k ; n <= n_max ; n++ ){

      ( fg_h[n] += f[d] * g_power[k][n] ) %= P;

    }
    
    if( ++k == K || d == N ){

      fg_h = Convolution( fg_h , g_power2[h] , N , P );

      for( uint n = 0 ; n <= N ; n++ ){

	( fg[n] += fg_h[n] ) < P ? 0 : fg[n] -= P;

      }
      
      k = 0;
      h++;
      n_max -= K;
      fg_h = vector<ll>( N + 1 );

    }

  }

  return fg;

}

inline void Solve()
{
  CEXPR( uint , bound_N , 1000 ); // 0が3個
  CIN_ASSERT( N , 1 , bound_N );
  CEXPR( ll , bound_M , 1000000000000000000 ); // 0が18個
  CIN_ASSERT( M , 1 , bound_M );
  CEXPR( ll , bound_P , 1000000000 ); // 0が9個
  CIN_ASSERT( P , N + 1 , bound_P );
  CEXPR( ll , bound_Ad , 1000000000000000000 ); // 0が18個
  vector<ll> A( N + 1 );
  FOREQ( d , 1 , N ){
    CIN_ASSERT( Ad , 0 , bound_Ad );
    A[d] = move( Ad %= P );
  }
  FACTORIAL_MOD( fact , fact_inv , inv , N , bound_N + 1 , P );
  vector<ll> arctan( N + 1 );
  FOREQ( d , 1 , N ){
    arctan[d] = d % 2 == 0 ? 0 : d % 4 == 1 ? inv[d] : P - inv[d];
  }
  vector<ll> sin( N + 1 );
  vector<ll> cos( N + 1 );
  FOREQ( d , 0 , N ){
    ( d % 2 == 0 ? cos : sin )[d] = d % 4 < 2 ? fact_inv[d] : P - fact_inv[d];
  }
  vector<ll> tan = Convolution( sin , Inverse( cos , N , P ) , N , P );
  A = Composite( arctan , A , N , P );
  M %= P;
  FOREQ( d , 1 , N ){
    ( A[d] *= M ) %= P;
  }
  A = Composite( tan , A , N , P );
  FOREQ( d , 1 , N ){
    cout << A[d] << " \n"[d==N];
  }
}

REPEAT_MAIN(1);
0