#920127 (C++17(gcc12)) No.3404 形式群法則

提出ソース
結果

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

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;
using ull = unsigned 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 ); \
    }									\
  }									\


#define SFINAE_FOR_POLYNOMIAL( DEFAULT )				\
  typename Arg , enable_if_t<is_constructible<T,decay_t<Arg> >::value>* DEFAULT \

template <typename T> class TruncatedPolynomial;

template <typename T>
class Polynomial
{

  friend class TruncatedPolynomial<T>;

protected:
  vector<T> m_f;
  // m_fのsize
  uint m_size;
  
public:
  inline Polynomial();
  inline Polynomial( const T& t );
  inline Polynomial( T&& t );
  template <SFINAE_FOR_POLYNOMIAL( = nullptr )> inline Polynomial( const Arg& n );
  inline Polynomial( const Polynomial<T>& f );
  inline Polynomial( Polynomial<T>&& f );
  inline Polynomial( const uint& i , const T& t );
  inline Polynomial( const uint& i , T&& t );
  template <SFINAE_FOR_POLYNOMIAL( = nullptr )> inline Polynomial( const uint& i , const Arg& n );
  inline Polynomial( const vector<T>& f );
  inline Polynomial( vector<T>&& f );

  inline Polynomial<T>& operator=( const T& t );
  inline Polynomial<T>& operator=( T&& t );
  template <SFINAE_FOR_POLYNOMIAL( = nullptr )> inline Polynomial<T>& operator=( const Arg& n );
  inline Polynomial<T>& operator=( const Polynomial<T>& f );
  inline Polynomial<T>& operator=( Polynomial<T>&& f );
  inline Polynomial<T>& operator=( const vector<T>& f );
  inline Polynomial<T>& operator=( vector<T>&& f );

  // 係数を参照。capacity変更時に不正な参照となるのでこの返り値を参照型の引数に渡す時は注意。
  inline const T& operator[]( const uint& i ) const;
  inline T& operator[]( const uint& i );

  // 代入
  inline T operator()( const T& t ) const;

  Polynomial<T>& operator+=( const Polynomial<T>& f );
  Polynomial<T>& operator-=( const Polynomial<T>& f );
  Polynomial<T>& operator*=( const Polynomial<T>& f );
  Polynomial<T>& operator*=( Polynomial<T>&& f );
  Polynomial<T>& operator/=( const T& t );
  inline Polynomial<T>& operator/=( const Polynomial<T>& f );
  Polynomial<T>& operator%=( const T& t );
  Polynomial<T>& operator%=( const Polynomial<T>& f );

  inline Polynomial<T> operator-() const;

  // XをX+tにshift
  // Tにおいてm_size未満の正整数が可逆である時のみサポート
  Polynomial<T>& operator<<=( const T& t );

  inline const vector<T>& GetCoefficient() const noexcept;
  inline const uint& size() const noexcept;

  inline void swap( Polynomial<T>& f );
  inline void swap( vector<T>& f );
  
  void RemoveRedundantZero();

  inline string Display() const noexcept;

  static Polynomial<T> Quotient( const Polynomial<T>& f0 , const Polynomial<T>& f1 );
  static Polynomial<T> TransposeQuotient( const Polynomial<T>& f0 , const uint& f0_transpose_size , const Polynomial<T>& f1_transpose_inverse , const uint& f1_size );
  static Polynomial<T> Transpose( const Polynomial<T>& f , const uint& f_transpose_size );

  static inline const Polynomial<T>& zero();
  static inline const T& const_zero();
  static inline const T& const_one();
  static inline const T& const_minus_one();

};

template <typename T>
bool operator==( const Polynomial<T>& f0 , const T& t1 );
template <typename T>
bool operator==( const Polynomial<T>& f0 , const Polynomial<T>& f1 );
template <typename T , typename P> inline bool operator!=( const Polynomial<T>& f0 , const P& f1 );

template <typename T , typename P> inline Polynomial<T> operator+( const Polynomial<T>& f0 , const P& f1 );
template <typename T , typename P> inline Polynomial<T> operator-( const Polynomial<T>& f );
template <typename T , typename P> inline Polynomial<T> operator-( const Polynomial<T>& f0 , const P& f1 );
template <typename T , typename P> inline Polynomial<T> operator*( const Polynomial<T>& f0 , const P& f1 );
template <typename T> inline Polynomial<T> operator/( const Polynomial<T>& f0 , const T& t1 );
template <typename T> inline Polynomial<T> operator/( const Polynomial<T>& f0 , const Polynomial<T>& f1 );
template <typename T , typename P> inline Polynomial<T> operator%( const Polynomial<T>& f0 , const P& f1 );
template <typename T> inline Polynomial<T> operator<<( const Polynomial<T>& f , const T& t );

// 多項式などの列の総乗を分割統治で計算し、その結果を第1成分に格納して参照返しする。
// V<T>はeraseを持つ必要がある。
template <typename T , template <typename...> typename V>
T& Prod( V<T>& f );


#define DEFINITION_BODY_OF_PARTIAL_SPECIALISATION_OF_MULTIPLICATION_OF_POLYNOMIAL_PROTH_MOD( TYPE , ARG , RHS ) \
  template <>								\
  Polynomial<TYPE>& Polynomial<TYPE>::operator*=( ARG f )		\
  {									\
									\
    if( m_size != 0 ){							\
									\
      vector<TYPE> v{};							\
      v.swap( m_f );							\
      TruncatedPolynomial<TYPE> this_copy{ m_size + f.m_size - 1 , move( v ) }; \
      this_copy *= RHS;							\
      m_f = move( this_copy.Polynomial<TYPE>::m_f );			\
      m_size = m_f.size();						\
									\
    }									\
									\
    return *this;							\
									\
  }									\
  
#define RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( CONDITION )	\
  if( CONDITION ){							\
									\
    return operator=( zero );						\
									\
  }									\
									\

#define RETURN_ZERO_FOR_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL_IF( CONDITION ) \
  if( CONDITION ){							\
									\
    return TruncatedPolynomial<T>( m_N );				\
									\
  }									\
									\

#define RETURN_ZERO_FOR__FOR_TRUNCATED_POLYNOMIAL_IF( MULTIPLICATION , CONDITION ) \
  RETURN_ZERO_FOR_ ## MULTIPLICATION ## _FOR_TRUNCATED_POLYNOMIAL_IF( CONDITION )	\


#define SET_VECTOR_FOR_ANSWER_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( N_OUTPUT_LIM ) \
  if( Polynomial<T>::m_size < N_OUTPUT_LIM ){				\
									\
    for( uint i = Polynomial<T>::m_size ; i < N_OUTPUT_LIM ; i++ ){	\
									\
      Polynomial<T>::m_f.push_back( 0 );				\
      									\
    }									\
    									\
    Polynomial<T>::m_size = N_OUTPUT_LIM;				\
    									\
  }									\


#define SET_VECTOR_FOR_ANSWER_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL( N_OUTPUT_LIM ) \
  vector<T> answer( N_OUTPUT_LIM )					\


#define SET_VECTOR_FOR_ANSWER_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION , N_OUTPUT_LIM ) \
  SET_VECTOR_FOR_ANSWER_OF_ ## MULTIPLICATION ## _FOR_TRUNCATED_POLYNOMIAL( N_OUTPUT_LIM ) \

#define SET_SUM_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL	\
  Polynomial<T>::m_f[i] = sum					\


#define SET_SUM_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL \
  answer[i] = sum							\


#define SET_SUM_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION )	\
  SET_SUM_OF_ ## MULTIPLICATION ## _FOR_TRUNCATED_POLYNOMIAL	\


#define SET_N_INPUT_START_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( F , SIZE , N_INPUT_START_NUM ) \
  uint N_INPUT_START_NUM{};						\
									\
  for( uint i = 0 ; i < SIZE && searching ; i++ ){			\
									\
    if( F[i] != zero ){							\
									\
      N_INPUT_START_NUM = i;						\
      searching = false;						\
									\
    }									\
									\
  }									\
									\


#define SET_N_INPUT_MAX_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( F , SIZE , N_INPUT_MAX_NUM ) \
  uint N_INPUT_MAX_NUM{};						\
  searching = true;							\
									\
  for( uint i = ( SIZE ) - 1 ; searching ; i-- ){			\
									\
    if( F[i] != zero ){							\
									\
      N_INPUT_MAX_NUM = i;						\
      searching = false;						\
									\
    }									\
									\
  }									\
									\


#define CONVOLUTION_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( J_MIN ) \
  const uint j_max = i < N_input_max_0_start_1 ? i - N_input_start_1 : N_input_max_0; \
  T sum{ zero };							\
									\
  for( uint j = J_MIN ; j <= j_max ; j++ ){				\
									\
    sum += Polynomial<T>::m_f[j] * f.Polynomial<T>::m_f[i - j];		\
									\
  }									\
									\
  Polynomial<T>::m_f[i] = sum;						\
									\


#define CONVOLUTION_FOR_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL( J_MIN ) \
  const uint j_max = i < N_input_max_0_start_1 ? i - N_input_start_1 : N_input_max_0; \
  T& m_fi = answer[i]; \
									\
  for( uint j = J_MIN ; j <= j_max ; j++ ){				\
									\
    m_fi += Polynomial<T>::m_f[j] * f.Polynomial<T>::m_f[i - j];	\
									\
  }									\
									\


#define CONVOLUTION_FOR__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION , J_MIN ) \
  CONVOLUTION_FOR_ ## MULTIPLICATION ## _FOR_TRUNCATED_POLYNOMIAL( J_MIN ) \


#define ZEROIFICATION_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL	\
  for( uint i = 0 ; i < N_input_start_0_start_1 ; i++ ){		\
									\
    Polynomial<T>::m_f[i] = 0;						\
									\
  }									\


#define ZEROIFICATION_FOR_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL \
  const uint& N_output_start_fixed = N_output_start < N_input_start_0_start_1 ? N_output_start : N_input_start_0_start_1; \
  									\
  for( uint i = 0 ; i < N_output_start_fixed ; i++ ){			\
									\
    answer[i] = 0;							\
									\
  }									\


#define ZEROIFICATION_FOR__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION )	\
  ZEROIFICATION_FOR_ ## MULTIPLICATION ## _FOR_TRUNCATED_POLYNOMIAL	\


#define DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION , ACCESS_ENTRY , N_OUTPUT_START ) \
  RETURN_ZERO_FOR__FOR_TRUNCATED_POLYNOMIAL_IF( MULTIPLICATION , Polynomial<T>::m_size == 0 ); \
  uint N_output_max = Polynomial<T>::m_size + f.Polynomial<T>::m_size - 2; \
									\
  if( N_output_max >= m_N ){						\
									\
    N_output_max = m_N - 1;						\
									\
  }									\
									\
  const uint N_output_lim = N_output_max + 1;				\
  SET_VECTOR_FOR_ANSWER_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION , N_output_lim ); \
									\
  for( uint i = N_output_max ; searching ; i-- ){			\
									\
    T sum{ zero };							\
									\
    for( uint j = 0 ; j <= i ; j++ ){					\
									\
      sum += ACCESS_ENTRY * f.Polynomial<T>::operator[]( i - j );	\
									\
    }									\
									\
    SET_SUM_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION );		\
    searching = i > N_OUTPUT_START;					\
									\
  }									\
  									\


#define DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION ) \
  SET_N_INPUT_START_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( Polynomial<T>::m_f , Polynomial<T>::m_size , N_input_start_0 ); \
  RETURN_ZERO_FOR__FOR_TRUNCATED_POLYNOMIAL_IF( MULTIPLICATION , searching ); \
  searching = true;							\
  SET_N_INPUT_START_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( f , f.Polynomial<T>::m_size , N_input_start_1 ); \
									\



#define SET_N_INPUT_RANGE						\
  SET_N_INPUT_MAX_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( Polynomial<T>::m_f , Polynomial<T>::m_size , N_input_max_0 ); \
  SET_N_INPUT_MAX_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( f , f.Polynomial<T>::m_size < m_N ? f.Polynomial<T>::m_size : m_N , N_input_max_1 ); \
  const uint N_input_max_0_max_1 = N_input_max_0 + N_input_max_1;	\
  const uint N_input_start_0_start_1 = N_input_start_0 + N_input_start_1; \
  uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N; \


#define DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION )	\
  const uint N_input_start_0_max_1 = N_input_start_0 + N_input_max_1;	\
  const uint N_input_max_0_start_1 = N_input_max_0 + N_input_start_1;	\
  const uint N_output_max_fixed = N_output_lim_fixed - 1;		\
  SET_VECTOR_FOR_ANSWER_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION , N_output_lim_fixed ); \
  									\
  for( uint i = N_output_max_fixed ; i > N_input_start_0_max_1 ; i-- ){	\
									\
    CONVOLUTION_FOR__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION , i - N_input_max_1 ); \
									\
  }									\
									\
  searching = true;							\
									\
  for( uint i = N_input_start_0_max_1 < N_output_max_fixed ? N_input_start_0_max_1 : N_output_max_fixed ; searching ; i-- ){ \
									\
    CONVOLUTION_FOR__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION , N_input_start_0 ); \
    searching = i > N_input_start_0_start_1;				\
									\
  }									\
									\
  ZEROIFICATION_FOR__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION );	\
									\

#define SET_SHIFTED_VECTOR_FOR_MULTIPLICATION( V , F , I_START , I_MAX , I_SHIFT ) \
  vector<T> V( product_length );					\
									\
  for( uint i = I_START ; i <= I_MAX ; i++ ){			\
									\
    V[I_SHIFT + i] = F[i];						\
									\
  }									\

#define DEFINITION_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( RETURN_LINE_0 , RETURN_LINE_1 , RETURN_LINE_2 , RETURN_LINE_3 , RETURN_LINE_4 , MULTIPLICATION , ACCESS_ENTRY , N_OUTPUT_START , FIX_N_OUTPUT_LIM ) \
  constexpr const uint& border_0 = Multiplication_border_0<T>;	\
  const T& zero = Polynomial<T>::const_zero();				\
  bool searching = true;						\
									\
  if( Polynomial<T>::m_size < border_0 && f.Polynomial<T>::m_size < border_0 ){ \
									\
    RETURN_LINE_0;							\
    DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION , ACCESS_ENTRY , N_OUTPUT_START ); \
    RETURN_LINE_1;							\
									\
  }									\
									\
  DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION );		\
  RETURN_LINE_2;							\
  SET_N_INPUT_RANGE;							\
  FIX_N_OUTPUT_LIM;							\
  RETURN_LINE_3;							\
  DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION );		\
  RETURN_LINE_4;							\


#define DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( TYPE , RECURSION ) \
  const uint& N = f.GetTruncation();					\
  uint power;								\
  uint power_2 = 1;							\
  TruncatedPolynomial< TYPE > f_inv{ power_2 , Polynomial< TYPE >::const_one() / f[0] }; \
									\
  while( power_2 < N ){							\
  									\
    power = power_2;							\
    power_2 *= 2;							\
    f_inv.SetTruncation( power_2 );					\
    RECURSION;								\
									\
  }									\
									\
  f_inv.SetTruncation( N );						\
  return f_inv							\
									\



#define DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( TYPE , RECURSION )	\
  const uint& N = f.GetTruncation();					\
  uint power;								\
  uint power_2 = 1;							\
  TruncatedPolynomial< TYPE > f_exp{ power_2 , Polynomial< TYPE >::const_one() }; \
									\
  while( power_2 < N ){							\
  									\
    power = power_2;							\
    power_2 *= 2;							\
    f_exp.SetTruncation( power_2 );					\
    RECURSION;								\
									\
  }									\
									\
  f_exp.SetTruncation( N );						\
  return f_exp							\
									\

template <typename T> class TruncatedPolynomial;

template <typename T> TruncatedPolynomial<T> Differential( const uint& n , const TruncatedPolynomial<T>& f );
template <typename T> TruncatedPolynomial<T> TruncatedDifferential( const TruncatedPolynomial<T>& f , const uint& N_output_start_plus_one );
template <typename T> TruncatedPolynomial<T> TruncatedIntegral( const TruncatedPolynomial<T>& f , const uint& N_output_start );

template <typename T>
class TruncatedPolynomial :
  public Polynomial<T>
{

  friend TruncatedPolynomial<T> Differential<T>( const uint& n , const TruncatedPolynomial<T>& f );
  friend TruncatedPolynomial<T> TruncatedDifferential<T>( const TruncatedPolynomial<T>& f , const uint& N_output_start_plus_one );
  friend TruncatedPolynomial<T> TruncatedIntegral<T>( const TruncatedPolynomial<T>& f , const uint& N_output_start );
  
private:
  // mod X^{m_N}で計算する。
  // m_N == 0でも動くが、その場合はm_size == 1の時にm_size <= m_Nが成り立たなくなることに注意
  uint m_N;
  
public:
  inline TruncatedPolynomial( const uint& N = 0 );
  inline TruncatedPolynomial( const TruncatedPolynomial<T>& f );
  inline TruncatedPolynomial( TruncatedPolynomial<T>&& f );
  inline TruncatedPolynomial( const uint& N , const T& t );
  inline TruncatedPolynomial( const uint& N , const Polynomial<T>& f );
  inline TruncatedPolynomial( const uint& N , Polynomial<T>&& f );
  inline TruncatedPolynomial( const uint& N , const uint& i , const T& t );
  inline TruncatedPolynomial( const uint& N , const uint& i , T&& t );
  template <SFINAE_FOR_POLYNOMIAL( = nullptr )> inline TruncatedPolynomial( const uint& N , const uint& i , const Arg& t );
  inline TruncatedPolynomial( const uint& N , vector<T>&& f );

  // m_Nも代入されることに注意
  inline TruncatedPolynomial<T>& operator=( const TruncatedPolynomial<T>& f );
  inline TruncatedPolynomial<T>& operator=( TruncatedPolynomial<T>&& f );
  inline TruncatedPolynomial<T>& operator=( const T& t );
  inline TruncatedPolynomial<T>& operator=( T&& t );
  template <SFINAE_FOR_POLYNOMIAL( = nullptr )> inline TruncatedPolynomial<T>& operator=( const Arg& n );
  inline TruncatedPolynomial<T>& operator=( const Polynomial<T>& f );
  inline TruncatedPolynomial<T>& operator=( Polynomial<T>&& f );

  // m_Nは変化しないことに注意
  inline TruncatedPolynomial<T>& operator+=( const T& t );
  inline TruncatedPolynomial<T>& operator+=( const Polynomial<T>& f );
  // m_N == 0の時のみm_Nが変化する。（内積などの計算の仕様）
  inline TruncatedPolynomial<T>& operator+=( const TruncatedPolynomial<T>& f );
  
  // N_input_lim <= f.size()の場合のみサポート。
  // 自身を(N_input_start個の0,f[N_input_start],...,f[N_input_lim-1],0,...)を足した値 mod X^{ m_N }で置き換える。
  TruncatedPolynomial<T>& TruncatedPlus( const Polynomial<T>& f , const uint& N_input_start , const uint& N_input_limit );

  // m_Nは変化しないことに注意
  inline TruncatedPolynomial<T>& operator-=( const T& t );
  inline TruncatedPolynomial<T>& operator-=( const Polynomial<T>& f );
  // m_N == 0の時のみm_Nが変化する。
  inline TruncatedPolynomial<T>& operator-=( const TruncatedPolynomial<T>& f );

  // N_input_lim <= f.size()の場合のみサポート。
  // 自身を(N_input_start個の0,f[N_input_start],...,f[N_input_lim-1],0,...)を引いた値 mod X^{ m_N }で置き換える。
  TruncatedPolynomial<T>& TruncatedMinus( const Polynomial<T>& f , const uint& N_input_start , const uint& N_input_limit );

  inline TruncatedPolynomial<T>& operator*=( const T& t );

  // m_N > 0の場合のみサポート。
  TruncatedPolynomial<T>& operator*=( const Polynomial<T>& f );
  inline TruncatedPolynomial<T>& operator*=( Polynomial<T>&& f );

  // m_N > 0かつf != 0の場合のみサポート。
  // 自身をf倍した値をhとし、長さm_Nの配列
  // (f[0],...,f[N_output_start-1],h[N_output_start],...,h[N_output_lim - 1],0,...)
  // で自身を置き換える。
  TruncatedPolynomial<T>& TruncatedMultiplication( const Polynomial<T>& f , const uint& N_output_start , const uint& N_output_lim );
    
  // m_N > 0の場合のみサポート。
  // 自身をf倍した値をhとし、長さm_Nの配列
  // (N_output_start個の0,h[N_output_start],...,h[N_output_lim - 1],0,...)
  // を返す。
  TruncatedPolynomial<T> TruncatedMultiplication_const( const Polynomial<T>& f , const uint& N_output_start , const uint& N_output_lim ) const;

  inline TruncatedPolynomial<T>& operator/=( const T& t );
  // Polynomialとしての商でないことに注意。
  inline TruncatedPolynomial<T>& operator/=( const TruncatedPolynomial<T>& t );
  inline TruncatedPolynomial<T>& operator%=( const T& t );

  inline TruncatedPolynomial<T> operator-() const;

  // 合成
  inline TruncatedPolynomial<T> operator()( const TruncatedPolynomial<T>& f ) const;

  inline void SetTruncation( const uint& N ) noexcept;
  inline const uint& GetTruncation() const noexcept;

  // N次未満を0に変更。
  inline TruncatedPolynomial<T>& TruncateInitial( const uint& N ) noexcept;
  // N次以上を0に変更。
  inline TruncatedPolynomial<T>& TruncateFinal( const uint& N ) noexcept;

};

template <typename T> inline constexpr const uint Multiplication_border_0 = 17;

template <typename T , typename P> inline TruncatedPolynomial<T> operator+( const TruncatedPolynomial<T>& f0 , const P& f1 );
template <typename T , typename P> inline TruncatedPolynomial<T> operator-( const TruncatedPolynomial<T>& f );
template <typename T , typename P> inline TruncatedPolynomial<T> operator-( const TruncatedPolynomial<T>& f0 , const P& f1 );
template <typename T , typename P> inline TruncatedPolynomial<T> operator*( const TruncatedPolynomial<T>& f0 , const P& f1 );
template <typename T , typename P> inline TruncatedPolynomial<T> operator/( const TruncatedPolynomial<T>& f0 , const P& f1 );
template <typename T> inline TruncatedPolynomial<T> operator%( const TruncatedPolynomial<T>& f0 , const T& t1 );

// m_Nが1下がることに注意。
template <typename T> inline TruncatedPolynomial<T> Differential( const TruncatedPolynomial<T>& f );
// m_Nがn下がることに注意。
template <typename T> inline TruncatedPolynomial<T> Differential( const uint& n , const TruncatedPolynomial<T>& f );
// m_Nが1下がることに注意。
// N_output_start_plus_one > 0の場合のみサポート。
template <typename T> TruncatedPolynomial<T> TruncatedDifferential( const TruncatedPolynomial<T>& f , const uint& N_output_start_plus_one );

// m_Nが1上がることに注意。
// Tが標数0またはf.m_N + 1以上の体の場合のみサポート。
template <typename T> inline TruncatedPolynomial<T> Integral( const TruncatedPolynomial<T>& f );
// m_Nが1上がることに注意。
// N_output_start > 0の場合のみサポート。
template <typename T>
TruncatedPolynomial<T> TruncatedIntegral( const TruncatedPolynomial<T>& f , const uint& N_output_start );

// f[0]が可逆な場合のみサポート。
template <typename T>
TruncatedPolynomial<T> Inverse( const TruncatedPolynomial<T>& f );

// Tが標数0またはf.m_N以上の体でかつf[0] == 0の場合のみサポート。
template <typename T>
TruncatedPolynomial<T> Exp( const TruncatedPolynomial<T>& f );

// Tが標数0またはf.m_N以上の体でかつf[0] == 1の場合のみサポート。
template <typename T> inline TruncatedPolynomial<T> Log( const TruncatedPolynomial<T>& f );

// Tが標数0またはf.m_N以上の体でかつf[0] == 1の場合のみサポート。
template <typename T>
TruncatedPolynomial<T> Power( const TruncatedPolynomial<T>& f , const T& t );

template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N ) : Polynomial<T>() , m_N( N ) { Polynomial<T>::m_f.reserve( m_N ); }
template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const TruncatedPolynomial<T>& f ) : Polynomial<T>( f ) , m_N( f.m_N ) { Polynomial<T>::m_f.reserve( m_N ); }
template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( TruncatedPolynomial<T>&& f ) : Polynomial<T>( move( f ) ) , m_N( move( f.m_N ) ) { Polynomial<T>::m_f.reserve( m_N ); }
template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N , const T& t ) : Polynomial<T>( t ) , m_N( N ) { Polynomial<T>::m_f.reserve( m_N ); }

template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N , const Polynomial<T>& f ) : Polynomial<T>() , m_N( N ) { Polynomial<T>::m_size = f.Polynomial<T>::m_size < m_N ? f.Polynomial<T>::m_size : m_N; Polynomial<T>::m_f = vector<T>( Polynomial<T>::m_size ); for( uint i = 0 ; i < Polynomial<T>::m_size ; i++ ){ Polynomial<T>::m_f[i] = f.Polynomial<T>::m_f[i]; } Polynomial<T>::m_f.reserve( m_N ); }

template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N , Polynomial<T>&& f ) : Polynomial<T>() , m_N( N ) { if( f.Polynomial<T>::m_size < m_N * 2 ){ Polynomial<T>::operator=( move( f ) ); if( f.Polynomial<T>::m_size < m_N ){ Polynomial<T>::m_f.reserve( m_N ); } else { TruncateFinal( m_N ); } } else { Polynomial<T>::m_f = vector<T>( m_N ); for( uint i = 0 ; i < m_N ; i++ ){ Polynomial<T>::m_f[i] = move( f.Polynomial<T>::m_f[i] ); } Polynomial<T>::m_size = m_N; } }

template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N , const uint& i , const T& t ) : Polynomial<T>() , m_N( N ) { if( i < m_N ? t != Polynomial<T>::const_zero() : false ){ Polynomial<T>::operator[]( i ) = t; } Polynomial<T>::m_f.reserve( m_N ); }

template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N , const uint& i , T&& t ) : Polynomial<T>() , m_N( N ) { if( i < m_N ? t != Polynomial<T>::const_zero() : false ){ Polynomial<T>::operator[]( i ) = move( t ); } Polynomial<T>::m_f.reserve( m_N ); }

template <typename T> template <SFINAE_FOR_POLYNOMIAL()> inline TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N , const uint& i , const Arg& n ) : TruncatedPolynomial( N , i , T( n ) ) {}

template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N , vector<T>&& f ) : Polynomial<T>() , m_N( N ) { const uint f_size = f.size(); if( f_size < m_N * 2 ){ Polynomial<T>::operator=( move( f ) ); if( f_size < m_N ){ Polynomial<T>::m_f.reserve( m_N ); } else { TruncateFinal( m_N ); } } else { Polynomial<T>::m_f = vector<T>( m_N ); for( uint i = 0 ; i < m_N ; i++ ){ Polynomial<T>::m_f[i] = move( f[i] ); } Polynomial<T>::m_f.reserve( m_N ); } }


template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator=( const TruncatedPolynomial<T>& f ) { Polynomial<T>::operator=( f ); m_N = f.m_N; Polynomial<T>::m_f.reserve( m_N ); return *this; }
template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator=( TruncatedPolynomial<T>&& f ) { Polynomial<T>::operator=( move( f ) ); m_N = move( f.m_N ); Polynomial<T>::m_f.reserve( m_N ); return *this; }
template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator=( const T& t ) { Polynomial<T>::operator=( t ); return *this; }
template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator=( T&& t ) { Polynomial<T>::operator=( move( t ) ); return *this; }
template <typename T> template <SFINAE_FOR_POLYNOMIAL()> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator=( const Arg& n ) { Polynomial<T>::operator=( T( n ) ); return *this; }
template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator=( const Polynomial<T>& f ) { return operator=( TruncatedPolynomial<T>( m_N , f ) ); }
template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator=( Polynomial<T>&& f ) { return operator=( TruncatedPolynomial<T>( m_N , move( f ) ) ); }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator+=( const T& t ) { Polynomial<T>::operator+=( t ); return *this; }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator+=( const Polynomial<T>& f ) { return TruncatedPolynomial<T>::TruncatedPlus( f , 0 , f.m_size ); }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator+=( const TruncatedPolynomial<T>& f ) { return m_N == 0 ? operator=( f ) : TruncatedPolynomial<T>::TruncatedPlus( f , 0 , f.Polynomial<T>::m_size ); }

template <typename T>
TruncatedPolynomial<T>& TruncatedPolynomial<T>::TruncatedPlus( const Polynomial<T>& f , const uint& N_input_start , const uint& N_input_lim )
{

  const uint& size = N_input_lim < m_N ? N_input_lim < f.Polynomial<T>::m_size ? N_input_lim : f.Polynomial<T>::m_size : m_N < f.Polynomial<T>::m_size ? m_N : f.Polynomial<T>::m_size;
  
  if( Polynomial<T>::m_size < size ){

    Polynomial<T>::m_f.reserve( size );

    for( uint i = N_input_start ; i < Polynomial<T>::m_size ; i++ ){

      Polynomial<T>::m_f[i] += f.Polynomial<T>::m_f[i];

    }

    for( uint i = Polynomial<T>::m_size ; i < size ; i++ ){
    
      Polynomial<T>::m_f.push_back( f.Polynomial<T>::m_f[i] );

    }

    Polynomial<T>::m_size = size;
    
  } else {

    for( uint i = N_input_start ; i < size ; i++ ){

      Polynomial<T>::m_f[i] += f.Polynomial<T>::m_f[i];

    }

  }
  
  return *this;

}

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator-=( const T& t ) { Polynomial<T>::operator-=( t ); return *this; }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator-=( const Polynomial<T>& f ) { return TruncatedPolynomial<T>::TruncatedMinus( f , 0 , f.m_size ); }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator-=( const TruncatedPolynomial<T>& f ) { return m_N == 0 ? operator=( -f ) : TruncatedPolynomial<T>::TruncatedMinus( f , 0 , f.Polynomial<T>::m_size ); }

template <typename T>
TruncatedPolynomial<T>& TruncatedPolynomial<T>::TruncatedMinus( const Polynomial<T>& f , const uint& N_input_start , const uint& N_input_lim )
{

  const uint& size = N_input_lim < m_N ? N_input_lim < f.Polynomial<T>::m_size ? N_input_lim : f.Polynomial<T>::m_size : m_N < f.Polynomial<T>::m_size ? m_N : f.Polynomial<T>::m_size;

  if( Polynomial<T>::m_size < size ){

    Polynomial<T>::m_f.reserve( size );

    for( uint i = N_input_start ; i < Polynomial<T>::m_size ; i++ ){

      Polynomial<T>::m_f[i] -= f.Polynomial<T>::m_f[i];

    }

    for( uint i = Polynomial<T>::m_size ; i < size ; i++ ){
    
      Polynomial<T>::m_f.push_back( - f.Polynomial<T>::m_f[i] );

    }

    Polynomial<T>::m_size = size;
    
  } else {

    for( uint i = N_input_start ; i < size ; i++ ){

      Polynomial<T>::m_f[i] -= f.Polynomial<T>::m_f[i];

    }

  }

  return *this;

}

template <typename T>
TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator*=( const Polynomial<T>& f )
{

  DEFINITION_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( f.Polynomial<T>::m_size == 0 ) , return *this , RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( searching ) , RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= m_N ) , return *this , MULTIPLICATION , Polynomial<T>::m_f[j] , 0 , );

}

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator*=( Polynomial<T>&& f ){ return operator*=( f ); }

template <typename T> 
TruncatedPolynomial<T>& TruncatedPolynomial<T>::TruncatedMultiplication( const Polynomial<T>& f , const uint& N_output_start , const uint& N_output_lim )
{
  
  DEFINITION_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( , return *this , , RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed ) , return *this , MULTIPLICATION , Polynomial<T>::m_f[j] , N_output_start , if( N_output_lim_fixed > N_output_lim ){ N_output_lim_fixed = N_output_lim; } );

}

template <typename T> 
TruncatedPolynomial<T> TruncatedPolynomial<T>::TruncatedMultiplication_const( const Polynomial<T>& f , const uint& N_output_start , const uint& N_output_lim ) const
{
  
  DEFINITION_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( , return TruncatedPolynomial<T>( m_N , move( answer ) ) , , RETURN_ZERO_FOR_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed ) , return TruncatedPolynomial<T>( m_N , move( answer ) ) , TRUNCATED_MULTIPLICATION_CONST , Polynomial<T>::operator[]( j ) , N_output_start , if( N_output_lim_fixed > N_output_lim ){ N_output_lim_fixed = N_output_lim; } );
  
}

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator/=( const T& t ) { Polynomial<T>::operator/=( t ); return *this; }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator/=( const TruncatedPolynomial<T>& f ) { return operator*=( Inverse( m_N > f.m_N ? f : TruncatedPolynomial<T>( m_N , f ) ) ); }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator%=( const T& t ) { Polynomial<T>::operator%=( t ); return *this; }

template <typename T> inline TruncatedPolynomial<T> TruncatedPolynomial<T>::operator-() const { return move( TruncatedPolynomial<T>( m_N ) -= *this ); }

template <typename T> inline TruncatedPolynomial<T> TruncatedPolynomial<T>::operator()( const TruncatedPolynomial<T>& f ) const
{

  assert( m_N > 0 );
  const uint N_minus = m_N - 1;

  if( N_minus == 0 ){

    return *this;

  }

  const uint H = sqrt( N_minus );
  const uint K = N_minus / H;
  vector<TruncatedPolynomial<T> > f_power( K < 2 ? 2 : K );
  ( f_power[1] = f ).SetTruncation( m_N );
  
  for( uint k = 2 ; k < K ; k++ ){

    f_power[k] = f_power[k-1] * f_power[1];

  }

  vector<TruncatedPolynomial<T> > f_power2( H + 1 );
  f_power2[1] = K < 2 ? f_power[1] : f_power[K-1] * f_power[1];

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

    f_power2[h] = f_power2[h-1] * f_power2[1];

  }

  uint k = 0;
  uint h = 0;
  uint n_max = N_minus;
  TruncatedPolynomial<T> answer{ m_N };
  TruncatedPolynomial<T> answer_h{ m_N };

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

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

      answer_h[n] += k == 0 ? n == 0 ? Polynomial<T>::m_f[d] : T{} : Polynomial<T>::m_f[d] * f_power[k][n];

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

      answer += h == 0 ? answer_h : answer_h *= f_power2[h];
      k = 0;
      h++;
      n_max -= K;
      answer_h = TruncatedPolynomial<T>( m_N );

    }

  }

  return answer;

}

template <typename T> inline void TruncatedPolynomial<T>::SetTruncation( const uint& N ) noexcept { if( N < m_N ){ TruncateFinal( m_N ); } else { Polynomial<T>::m_f.reserve( N ); } m_N = N; }
template <typename T> inline const uint& TruncatedPolynomial<T>::GetTruncation() const noexcept { return m_N; }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::TruncateInitial( const uint& N ) noexcept { const uint& size = N < Polynomial<T>::m_size ? N : Polynomial<T>::m_size; for( uint i = 0 ; i < size ; i++ ){ Polynomial<T>::m_f[i] = 0; } return *this; }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::TruncateFinal( const uint& N ) noexcept { while( Polynomial<T>::m_size > N ){ Polynomial<T>::m_f.pop_back(); Polynomial<T>::m_size--; } return *this; }

template <typename T , typename P> inline TruncatedPolynomial<T> operator+( const TruncatedPolynomial<T>& f0 , const P& f1 ) { return move( TruncatedPolynomial<T>( f0 ) += f1 ); }
template <typename T , typename P> inline TruncatedPolynomial<T> operator-( const TruncatedPolynomial<T>& f ) { return move( TruncatedPolynomial<T>( f.GetTurncation() ) -= f ); }
template <typename T , typename P> inline TruncatedPolynomial<T> operator-( const TruncatedPolynomial<T>& f0 , const P& f1 ) { return move( TruncatedPolynomial<T>( f0 ) -= f1 ); }
template <typename T , typename P> inline TruncatedPolynomial<T> operator*( const TruncatedPolynomial<T>& f0 , const P& f1 ) { return move( TruncatedPolynomial<T>( f0 ) *= f1 ); }
template <typename T , typename P> inline TruncatedPolynomial<T> operator/( const TruncatedPolynomial<T>& f0 , const P& f1 ) { return move( TruncatedPolynomial<T>( f0 ) /= f1 ); }
template <typename T> inline TruncatedPolynomial<T> operator%( const TruncatedPolynomial<T>& f0 , const T& t1 ) { return move( TruncatedPolynomial<T>( f0 ) %= t1 ); }


template <typename T> inline TruncatedPolynomial<T> Differential( const TruncatedPolynomial<T>& f ) { return TruncatedDifferential<T>( f , 1 ); }

template <typename T>
TruncatedPolynomial<T> Differential( const uint& n , const TruncatedPolynomial<T>& f )
{

  if( f.Polynomial<T>::m_size < n ){

    return TruncatedPolynomial<T>( f.m_N - n , Polynomial<T>::zero() );

  }

  vector<T> df( f.Polynomial<T>::m_size - n );
  T coef = T::Factorial( n );
  uint i = n;

  while( i < f.Polynomial<T>::m_size ){

    df[i - n] = f[i] * coef;
    i++;
    ( coef *= i ) /= ( i - n );

  }

  return TruncatedPolynomial<T>( f.m_N - n , move( df ) );

}

#define ERR_INPUT

template <typename T>
TruncatedPolynomial<T> TruncatedDifferential( const TruncatedPolynomial<T>& f , const uint& N_output_start_plus_one )
{

  if( f.m_N == 0 ){

    ERR_INPUT( f , f.m_N );

  }

  TruncatedPolynomial<T> f_dif{ f.m_N - 1 };

  if( N_output_start_plus_one < f.Polynomial<T>::m_size ){

    const uint size = f.Polynomial<T>::m_size - 1;
    f_dif.Polynomial<T>::m_f = vector<T>( size );

    for( uint i = N_output_start_plus_one ; i < f.Polynomial<T>::m_size ; i++ ){

      f_dif.Polynomial<T>::m_f[i-1] = f.Polynomial<T>::m_f[i] * i;

    }

    f_dif.Polynomial<T>::m_size = size;

  }

  return f_dif;

}

template <typename T> inline TruncatedPolynomial<T> Integral( const TruncatedPolynomial<T>& f ) { return TruncatedIntegral<T>( f , 1 ); }

template <typename T>
TruncatedPolynomial<T> TruncatedIntegral( const TruncatedPolynomial<T>& f , const uint& N_output_start )
{

  TruncatedPolynomial<T> f_int{ f.m_N + 1 };

  if( N_output_start <= f.Polynomial<T>::m_size ){

    const uint size = f.Polynomial<T>::m_size + 1;
    f_int.Polynomial<T>::m_f = vector<T>( size );
    
    for( uint i = N_output_start ; i <= f.Polynomial<T>::m_size ; i++ ){

      f_int.Polynomial<T>::m_f[i] = f.Polynomial<T>::m_f[i - 1] / T( i );

    }

    f_int.Polynomial<T>::m_size = size;
    
  }

  return f_int;

}

template <typename T>
TruncatedPolynomial<T> Inverse( const TruncatedPolynomial<T>& f )
{

  DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( T , f_inv.TruncatedMinus( f_inv.TruncatedMultiplication_const( f , power , power_2 ).TruncatedMultiplication( f_inv , power , power_2 ) , power , power_2 ) );
  
}

template <typename T>
TruncatedPolynomial<T> Exp( const TruncatedPolynomial<T>& f )
{

  DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( T , f_exp.TruncatedMinus( ( TruncatedIntegral( Differential( f_exp ).TruncatedMultiplication_const( Inverse( f_exp ) , power - 1 , power_2 ) , power ).TruncatedMinus( f , power , power_2 ) ).TruncatedMultiplication( f_exp , power ) , power , power_2 ) );
  
}

template <typename T> inline TruncatedPolynomial<T> Log( const TruncatedPolynomial<T>& f ) { return Integral<T>( Differential<T>( f ) /= f ); }

template <typename T> inline TruncatedPolynomial<T> Power( const TruncatedPolynomial<T>& f , const T& t ) { return Exp( Log( f ) *= t ); }


template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator*=( const T& t ) { Polynomial<T>::operator*=( t ); return *this; }

template <typename T> inline Polynomial<T>::Polynomial() : m_f() , m_size( 0 ) {}
template <typename T> inline Polynomial<T>::Polynomial( const T& t ) : Polynomial() { if( t != const_zero() ){ operator[]( 0 ) = t; } }
template <typename T> inline Polynomial<T>::Polynomial( T&& t ) : Polynomial() { if( t != const_zero() ){ operator[]( 0 ) = move( t ); } }
template <typename T> template <SFINAE_FOR_POLYNOMIAL()> inline Polynomial<T>::Polynomial( const Arg& n ) : Polynomial( T( n ) ) {}
template <typename T> inline Polynomial<T>::Polynomial( const Polynomial<T>& f ) : m_f( f.m_f ) , m_size( f.m_size ) {}
template <typename T> inline Polynomial<T>::Polynomial( Polynomial<T>&& f ) : m_f( move( f.m_f ) ) , m_size( move( f.m_size ) ) {}
template <typename T> inline Polynomial<T>::Polynomial( const uint& i , const T& t ) : Polynomial() { if( t != const_zero() ){ operator[]( i ) = t; } }
template <typename T> inline Polynomial<T>::Polynomial( const uint& i , T&& t ) : Polynomial() { if( t != const_zero() ){ operator[]( i ) = move( t ); } }
template <typename T> template <SFINAE_FOR_POLYNOMIAL()> inline Polynomial<T>::Polynomial( const uint& i , const Arg& n ) : Polynomial( i , T( n ) ) {}
template <typename T> inline Polynomial<T>::Polynomial( const vector<T>& f ) : m_f( f ) , m_size( m_f.size() ) {}
template <typename T> inline Polynomial<T>::Polynomial( vector<T>&& f ) : m_f( move( f ) ) , m_size( m_f.size() ) {}


template <typename T> inline Polynomial<T>& Polynomial<T>::operator=( const T& t ) { m_f.clear(); m_size = 0; operator[]( 0 ) = t; return *this; }
template <typename T> inline Polynomial<T>& Polynomial<T>::operator=( T&& t ) { m_f.clear(); m_size = 0; operator[]( 0 ) = move( t ); return *this; }
template <typename T> template <SFINAE_FOR_POLYNOMIAL()> inline Polynomial<T>& Polynomial<T>::operator=( const Arg& n ) { return operator=( T( n ) ); }
template <typename T> inline Polynomial<T>& Polynomial<T>::operator=( const Polynomial<T>& f ) { m_f = f.m_f; m_size = f.m_size; return *this; }
template <typename T> inline Polynomial<T>& Polynomial<T>::operator=( Polynomial<T>&& f ) { m_f = move( f.m_f ); m_size = move( f.m_size ); return *this; }
template <typename T> inline Polynomial<T>& Polynomial<T>::operator=( const vector<T>& f ) { m_f = f; m_size = f.m_size; return *this; }
template <typename T> inline Polynomial<T>& Polynomial<T>::operator=( vector<T>&& f ) { m_f = move( f ); m_size = m_f.size(); return *this; }


template <typename T>
const T& Polynomial<T>::operator[]( const uint& i ) const
{

  if( m_size <= i ){

    return const_zero();

  }
  
  return m_f[i];

}

template <typename T> inline T& Polynomial<T>::operator[]( const uint& i )
{

  if( m_size <= i ){
    
    const T& z = const_zero();

    while( m_size <= i ){

      m_f.push_back( z );
      m_size++;
    
    }

  }

  return m_f[i];

}

template <typename T> inline T Polynomial<T>::operator()( const T& t ) const { return move( ( *this % ( Polynomial<T>( 1 , const_one() ) - t ) )[0] ); }

template <typename T>
Polynomial<T>& Polynomial<T>::operator+=( const Polynomial<T>& f )
{

  if( m_size < f.m_size ){

    m_f.reserve( f.m_size );

    for( uint i = 0 ; i < m_size ; i++ ){

      m_f[i] += f.m_f[i];

    }

    for( uint i = m_size ; i < f.m_size ; i++ ){

      m_f.push_back( f.m_f[i] );

    }

    m_size = f.m_size;

  } else {

    for( uint i = 0 ; i < f.m_size ; i++ ){

      m_f[i] += f.m_f[i];

    }

  }

  return *this;

}

template <typename T>
Polynomial<T>& Polynomial<T>::operator-=( const Polynomial<T>& f )
{

  if( m_size < f.m_size ){

    m_f.reserve( f.m_size );

    for( uint i = 0 ; i < m_size ; i++ ){

      m_f[i] -= f.m_f[i];

    }

    for( uint i = m_size ; i < f.m_size ; i++ ){

      m_f.push_back( - f.m_f[i] );

    }

    m_size = f.m_size;

  } else {

    for( uint i = 0 ; i < f.m_size ; i++ ){

      m_f[i] -= f.m_f[i];

    }

  }

  return *this;

}

template <typename T>
Polynomial<T>& Polynomial<T>::operator*=( const Polynomial<T>& f )
{
  
  if( m_size == 0 ){

    return *this;

  }

  if( f.m_size == 0 ){

    m_f.clear();
    m_size = 0;
    return *this;

  }
  
  const uint size = m_size + f.m_size - 1;
  Polynomial<T> product{};  
  
  for( uint i = 0 ; i < size ; i++ ){

    T& product_i = product[i];
    const uint j_min = m_size > i ? 0 : i - m_size + 1;
    const uint j_lim = i < f.m_size ? i + 1 : f.m_size;
      
    for( uint j = j_min ; j < j_lim ; j++ ){
	
      product_i += m_f[i - j] * f.m_f[j];

    }

  }

  return operator=( move( product ) );

}

template <typename T> inline Polynomial<T>& Polynomial<T>::operator*=( Polynomial<T>&& f ) { return operator*=( f ); };

template <typename T>
Polynomial<T>& Polynomial<T>::operator/=( const T& t )
{
  
  if( t == const_one() ){

    return *this;

  }

  const T t_inv{ const_one() / t };
  
  for( uint i = 0 ; i < m_size ; i++ ){

    operator[]( i ) *= t_inv;

  }

  return *this;

}

template <typename T>
Polynomial<T> Polynomial<T>::Transpose( const Polynomial<T>& f , const uint& f_transpose_size )
{

  vector<T> f_transpose( f_transpose_size );

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

    f_transpose[d] = f.m_f[f.m_size - 1 - d];

  }

  return Polynomial<T>( move( f_transpose ) );

}

template <typename T>
Polynomial<T>& Polynomial<T>::operator%=( const T& t )
{

  if( t == const_one() ){

    return operator=( zero() );

  }
  
  for( uint i = 0 ; i < m_size ; i++ ){

    m_f[i] %= t;

  }

  return *this;

}

template <typename T> inline Polynomial<T> Polynomial<T>::operator-() const { return move( Polynomial<T>() -= *this ); }

template <typename T> inline const vector<T>& Polynomial<T>::GetCoefficient() const noexcept { return m_f; }
template <typename T> inline const uint& Polynomial<T>::size() const noexcept { return m_size; }

template <typename T> inline void Polynomial<T>::swap( Polynomial<T>& f ) { m_f.swap( f.m_f ); swap( m_size , f.m_size ); }
template <typename T> inline void Polynomial<T>::swap( vector<T>& f ) { m_f.swap( f ); m_size = m_f.size(); }


template <typename T>
void Polynomial<T>::RemoveRedundantZero()
{

  const T& z = const_zero();
  
  while( m_size > 0 ? m_f[m_size - 1] == z : false ){

    m_f.pop_back();
    m_size--;

  }

  return;

}

template <typename T>
string Polynomial<T>::Display() const noexcept
{

  string s = "(";

  if( m_size > 0 ){

    s += to_string( m_f[0] );

    for( uint i = 1 ; i < m_size ; i++ ){

      s += ", " + to_string( m_f[i] );

    }

  }

  s += ")";
  return s;

}


template <typename T> inline const Polynomial<T>& Polynomial<T>::zero() { static const Polynomial<T> z{}; return z; }
template <typename T> inline const T& Polynomial<T>::const_zero() { static const T z{ 0 }; return z; }
template <typename T> inline const T& Polynomial<T>::const_one() { static const T o{ 1 }; return o; }
template <typename T> inline const T& Polynomial<T>::const_minus_one() { static const T m{ -1 }; return m; }

template <typename T>
bool operator==( const Polynomial<T>& f0 , const T& t1 )
{

  const uint& size = f0.size();
  const T& zero = Polynomial<T>::const_zero();

  for( uint i = 1 ; i < size ; i++ ){

    if( f0[i] != zero ){

      return false;

    }

  }

  return f0[0] == t1;

}

template <typename T>
bool operator==( const Polynomial<T>& f0 , const Polynomial<T>& f1 )
{

  const uint& size0 = f0.size();
  const uint& size1 = f1.size();
  const uint& size = size0 < size1 ? size1 : size0;

  for( uint i = 0 ; i < size ; i++ ){

    if( f0[i] != f1[i] ){

      return false;

    }

  }

  return true;

}

template <typename T , typename P> inline bool operator!=( const Polynomial<T>& f0 , const P& f1 ) { return !( f0 == f1 ); }

template <typename T , typename P> inline Polynomial<T> operator+( const Polynomial<T>& f0 , const P& f1 ) { return move( Polynomial<T>( f0 ) += f1 ); }
template <typename T , typename P> inline Polynomial<T> operator-( const Polynomial<T>& f ) { return Polynomial<T>::zero() - f; }
template <typename T , typename P> inline Polynomial<T> operator-( const Polynomial<T>& f0 , const P& f1 ) { return move( Polynomial<T>( f0 ) -= f1 ); }
template <typename T , typename P> inline Polynomial<T> operator*( const Polynomial<T>& f0 , const P& f1 ) { return move( Polynomial<T>( f0 ) *= f1 ); }
template <typename T> inline Polynomial<T> operator/( const Polynomial<T>& f0 , const T& t1 ) { return move( Polynomial<T>( f0 ) /= t1 ); }

template <typename T , template <typename...> typename V>
T& Prod( V<T>& f )
{

  if( f.empty() ){

    f.push_back( T( 1 ) );

  }

  if( f.size() == 1 ){

    return f.front();

  }

  auto itr = f.begin() , end = f.end();
  
  while( itr != end ){

    T& t = *itr;
    itr++;

    if( itr != end ){

      t *= *itr;
      itr = f.erase( itr );
      
    }

  }

  return Prod( f );

}


// 以下TruncatedPolynomial<T>を使用。
template <typename T> inline Polynomial<T>& Polynomial<T>::operator/=( const Polynomial<T>& f ) { return m_size < f.m_size ? *this : operator=( Quotient( *this , f ) ); }

template <typename T>
Polynomial<T> Polynomial<T>::Quotient( const Polynomial<T>& f0 , const Polynomial<T>& f1 )
{

  if( f0.m_size < f1.m_size ){

    return f0;

  }

  if( f1.m_size == 0 ){

    ERR_INPUT( f0 , f1 , f1.m_size );

  }

  const uint f0_transpose_size = f0.m_size - f1.m_size + 1;
  const uint f1_transpose_size = f0_transpose_size < f1.m_size ? f0_transpose_size : f1.m_size;
  return TransposeQuotient( f0 , f0_transpose_size , Inverse( TruncatedPolynomial<T>( f0_transpose_size , Transpose( f1 , f1_transpose_size ) ) ) , f1.m_size );

}

template <typename T>
Polynomial<T> Polynomial<T>::TransposeQuotient( const Polynomial<T>& f0 , const uint& f0_transpose_size , const Polynomial<T>& f1_transpose_inverse , const uint& f1_size )
{

  TruncatedPolynomial<T> f0_transpose{ f0_transpose_size , Transpose( f0 , f0_transpose_size ) };
  f0_transpose *= f1_transpose_inverse;

  for( uint d0 = ( f0_transpose_size + 1 ) / 2 ; d0 < f0_transpose_size ; d0++ ){

    ::swap( f0_transpose.Polynomial<T>::m_f[d0] , f0_transpose.Polynomial<T>::m_f[ f0_transpose_size - 1 - d0 ] );

  }

  return f0_transpose;

}

template <typename T>
Polynomial<T>& Polynomial<T>::operator%=( const Polynomial<T>& f )
{

  if( m_size >= f.m_size ){

    operator-=( ( *this / f ) * f );
    RemoveRedundantZero();

  }

  return *this;

}

template <typename T >
Polynomial<T>& Polynomial<T>::operator<<=( const T& t )
{

  if( m_size > 0 ){

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

      m_f[d] *= T::Factorial( d );

    }

    TruncatedPolynomial<T> exp_t_transpose{ m_size * 2 };
    T power_t = const_one();
  
    for( uint d = 0 ; d < m_size ; d++ ){

      exp_t_transpose[m_size - 1 - d] = power_t * T::FactorialInverse( d );
      power_t *= t;

    }

    exp_t_transpose *= *this;
  
    for( uint d = 0 ; d < m_size ; d++ ){

      m_f[d] = exp_t_transpose.Polynomial<T>::m_f[d + m_size - 1] * T::FactorialInverse( d );

    }

  }

  return *this;

}

template <typename T> inline Polynomial<T> operator/( const Polynomial<T>& f0 , const Polynomial<T>& f1 ) { return Polynomial<T>::Quotient( f0 , f1 ); }
template <typename T , typename P> inline Polynomial<T> operator%( const Polynomial<T>& f0 , const P& f1 ) { return move( Polynomial<T>( f0 ) %= f1 ); }
template <typename T> Polynomial<T> operator<<( const Polynomial<T>& f , const T& t ) { return move( Polynomial<T>( f ) <<= t ); };


template <typename INT>
class QuotientRing
{

protected:
  INT m_n;
  const INT* m_p_M;

public:
  inline QuotientRing() noexcept;
  inline QuotientRing( const INT& n , const INT* const& p_M = nullptr ) noexcept;
  inline QuotientRing( const QuotientRing<INT>& n ) noexcept;

  inline QuotientRing<INT>& operator+=( const QuotientRing<INT>& n ) noexcept;
  inline QuotientRing<INT>& operator+=( const INT& n ) noexcept;
  // operator<が定義されていても負の数は正に直さず剰余を取ることに注意。
  inline QuotientRing<INT>& operator-=( const QuotientRing<INT>& n ) noexcept;
  inline QuotientRing<INT>& operator-=( const INT& n ) noexcept;
  inline QuotientRing<INT>& operator*=( const QuotientRing<INT>& n ) noexcept;
  inline QuotientRing<INT>& operator*=( const INT& n ) noexcept;
  // *m_p_Mが素数でかつnの逆元が存在する場合のみサポート。
  inline QuotientRing<INT>& operator/=( const QuotientRing<INT>& n );
  inline QuotientRing<INT>& operator/=( const INT& n );

  // m_nの正負やm_p_Mの一致込みの等号。
  inline bool operator==( const QuotientRing<INT>& n ) const noexcept;
  inline bool operator!=( const QuotientRing<INT>& n ) const noexcept;

  template <typename T> inline QuotientRing<INT> operator+( const T& n1 ) const noexcept;
  inline QuotientRing<INT> operator-() const noexcept;
  template <typename T> inline QuotientRing<INT> operator-( const T& n1 ) const noexcept;
  template <typename T> inline QuotientRing<INT> operator*( const T& n1 ) const noexcept;
  // *m_p_Mが素数でかつn1の逆元が存在する場合のみサポート。
  template <typename T> inline QuotientRing<INT> operator/( const T& n1 ) const;

  inline const INT& Represent() const noexcept;
  inline const INT& GetModulo() const noexcept;
  inline void SetModulo( const INT* const& p_M = nullptr ) noexcept;

  template <typename T> static QuotientRing<INT> Power( const QuotientRing<INT>& n , T exponent );
  // *m_p_Mが素数でかつnの逆元が存在する場合のみサポート。
  static QuotientRing<INT> Inverse( const QuotientRing<INT>& n );
  
};

template <typename INT , typename T> inline QuotientRing<INT> Power( const QuotientRing<INT>& n , T exponent );
// *(n.m_p_M)が素数でかつnの逆元が存在する場合のみサポート。
template <typename INT> inline QuotientRing<INT> Inverse( const QuotientRing<INT>& n );

template <typename INT> inline QuotientRing<INT>::QuotientRing() noexcept : m_n() , m_p_M( nullptr ) {}
template <typename INT> inline QuotientRing<INT>::QuotientRing( const INT& n , const INT* const& p_M ) noexcept : m_n( p_M == nullptr ? n : n % *p_M ) , m_p_M( p_M ) {}
template <typename INT> inline QuotientRing<INT>::QuotientRing( const QuotientRing<INT>& n ) noexcept : m_n( n.m_n ) , m_p_M( n.m_p_M ) {}

template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator+=( const QuotientRing<INT>& n ) noexcept { if( m_p_M == nullptr ){ m_p_M = n.m_p_M; } m_n += n.m_n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator+=( const INT& n ) noexcept { m_n += n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator-=( const QuotientRing<INT>& n ) noexcept { if( m_p_M == nullptr ){ m_p_M = n.m_p_M; } m_n -= n.m_n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator-=( const INT& n ) noexcept { m_n -= n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator*=( const QuotientRing<INT>& n ) noexcept { if( m_p_M == nullptr ){ m_p_M = n.m_p_M; } m_n *= n.m_n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator*=( const INT& n ) noexcept { m_n *= n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator/=( const QuotientRing<INT>& n ) { if( m_p_M == nullptr ){ if( n.m_p_M == nullptr ){ assert( n.m_n != 0 ); m_n /= n.m_n; return *this; } else { m_p_M = n.m_p_M; } } return operator*=( Inverse( QuotientRing<INT>( n.m_n , m_p_M ) ) ); }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator/=( const INT& n ) { if( m_p_M == nullptr ){ assert( n.m_n != 0 ); m_n /= n.m_n; return *this; } return operator*=( Inverse( Q( n.m_n , m_p_M ) ) ); }

template <typename INT> inline bool QuotientRing<INT>::operator==( const QuotientRing<INT>& n ) const noexcept { return m_p_M == n.m_p_M && m_n == n.m_n; }
template <typename INT> inline bool QuotientRing<INT>::operator!=( const QuotientRing<INT>& n ) const noexcept { return !operator==( n ); }

template <typename INT> template<typename T> inline QuotientRing<INT> QuotientRing<INT>::operator+( const T& n ) const noexcept { return QuotientRing<INT>( *this ).operator+=( n ); }
template <typename INT> inline QuotientRing<INT> QuotientRing<INT>::operator-() const noexcept { return QuotientRing<INT>( -m_n , m_p_M ); }
template <typename INT> template<typename T> inline QuotientRing<INT> QuotientRing<INT>::operator-( const T& n ) const noexcept { return QuotientRing<INT>( *this ).operator-=( n ); }
template <typename INT> template<typename T> inline QuotientRing<INT> QuotientRing<INT>::operator*( const T& n ) const noexcept { return QuotientRing<INT>( *this ).operator*=( n ); }
template <typename INT> template<typename T> inline QuotientRing<INT> QuotientRing<INT>::operator/( const T& n ) const { return QuotientRing<INT>( *this ).operator/=( n ); }
  
template <typename INT> inline const INT& QuotientRing<INT>::Represent() const noexcept { return m_n; }
template <typename INT> inline const INT& QuotientRing<INT>::GetModulo() const noexcept { static const INT zero{ 0 }; return m_p_M == nullptr ? zero : *m_p_M; }
template <typename INT> inline void QuotientRing<INT>::SetModulo( const INT* const& p_M ) noexcept { m_p_M = p_M; if( m_p_M != nullptr ){ m_n %= *m_p_M; } }

template <typename INT> template <typename T>
QuotientRing<INT> QuotientRing<INT>::Power( const QuotientRing<INT>& n , T exponent )
{

  QuotientRing<INT> answer{ 1 , n.m_p_M };
  QuotientRing<INT> power{ n };

  while( exponent != 0 ){

    if( exponent % 2 == 1 ){

      answer *= power;

    }

    power *= power;
    exponent /= 2;

  }

  return answer;

}

template <typename INT> inline QuotientRing<INT> QuotientRing<INT>::Inverse( const QuotientRing<INT>& n ) { assert( n.m_p_M != nullptr ); return Power( n , *( n.m_p_M ) - 2 ); }

template <typename INT , typename T> inline QuotientRing<INT> Power( const QuotientRing<INT>& n , T exponent ) { return QuotientRing<INT>::template Power<T>( n , exponent ); }
template <typename INT> inline QuotientRing<INT> Inverse( const QuotientRing<INT>& n ) { return QuotientRing<INT>::Inverse( n ); }


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_Ai , 1000000000000000000 ); // 0が18個
  using Q = QuotientRing<ll>;
  using TRPOQ = TruncatedPolynomial<Q>;
  TRPOQ A{ N + 1 };
  FOREQ( d , 1 , N ){
    CIN_ASSERT( Ai , 0 , bound_Ai );
    A[d] = Q( Ai , &P );
  }
  FACTORIAL_MOD( fact , fact_inv , inv , N , bound_N + 1 , P );
  TRPOQ arctan{ N + 1 };
  FOREQ( d , 1 , N ){
    arctan[d] = Q( d % 2 == 0 ? 0 : d % 4 == 1 ? inv[d] : P - inv[d] , &P );
  }
  TRPOQ sin{ N + 1 };
  TRPOQ cos{ N + 1 };
  FOREQ( d , 0 , N ){
    ( d % 2 == 0 ? cos : sin )[d] = Q( d % 4 < 2 ? fact_inv[d] : P - fact_inv[d] , &P );
  }
  TRPOQ tan = sin / cos;
  A = tan( arctan( A ) * Q( M , &P ) );
  FOREQ( d , 1 , N ){
    ll Ad = A[d].Represent();
    cout << ( Ad < 0 ? Ad += P : Ad ) << " \n"[d==N];
  }
}

REPEAT_MAIN(1);
yukicoder

結果

ソースコード
