#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 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 #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 inline basic_istream& VariadicCin( basic_istream& is ) { return is; } template inline basic_istream& VariadicCin( basic_istream& is , Arg& arg , ARGS&... args ) { return VariadicCin( is >> arg , args... ); } template inline basic_istream& VariadicGetline( basic_istream& is , const char& separator ) { return is; } template inline basic_istream& VariadicGetline( basic_istream& is , const char& separator , Arg& arg , ARGS&... args ) { return VariadicGetline( getline( is , arg , separator ) , separator , args... ); } template inline basic_ostream& VariadicCout( basic_ostream& os , const Arg& arg ) { return os << arg; } template inline basic_ostream& VariadicCout( basic_ostream& 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 >::value>* DEFAULT \ template class TruncatedPolynomial; template class Polynomial { friend class TruncatedPolynomial; protected: vector m_f; // m_fのsize uint m_size; public: inline Polynomial(); inline Polynomial( const T& t ); inline Polynomial( T&& t ); template inline Polynomial( const Arg& n ); inline Polynomial( const Polynomial& f ); inline Polynomial( Polynomial&& f ); inline Polynomial( const uint& i , const T& t ); inline Polynomial( const uint& i , T&& t ); template inline Polynomial( const uint& i , const Arg& n ); inline Polynomial( const vector& f ); inline Polynomial( vector&& f ); inline Polynomial& operator=( const T& t ); inline Polynomial& operator=( T&& t ); template inline Polynomial& operator=( const Arg& n ); inline Polynomial& operator=( const Polynomial& f ); inline Polynomial& operator=( Polynomial&& f ); inline Polynomial& operator=( const vector& f ); inline Polynomial& operator=( vector&& f ); // 係数を参照。capacity変更時に不正な参照となるのでこの返り値を参照型の引数に渡す時は注意。 inline const T& operator[]( const uint& i ) const; inline T& operator[]( const uint& i ); // 代入 inline T operator()( const T& t ) const; Polynomial& operator+=( const Polynomial& f ); Polynomial& operator-=( const Polynomial& f ); Polynomial& operator*=( const Polynomial& f ); Polynomial& operator*=( Polynomial&& f ); Polynomial& operator/=( const T& t ); inline Polynomial& operator/=( const Polynomial& f ); Polynomial& operator%=( const T& t ); Polynomial& operator%=( const Polynomial& f ); inline Polynomial operator-() const; // XをX+tにshift // Tにおいてm_size未満の正整数が可逆である時のみサポート Polynomial& operator<<=( const T& t ); inline const vector& GetCoefficient() const noexcept; inline const uint& size() const noexcept; inline void swap( Polynomial& f ); inline void swap( vector& f ); void RemoveRedundantZero(); inline string Display() const noexcept; static Polynomial Quotient( const Polynomial& f0 , const Polynomial& f1 ); static Polynomial TransposeQuotient( const Polynomial& f0 , const uint& f0_transpose_size , const Polynomial& f1_transpose_inverse , const uint& f1_size ); static Polynomial Transpose( const Polynomial& f , const uint& f_transpose_size ); static inline const Polynomial& zero(); static inline const T& const_zero(); static inline const T& const_one(); static inline const T& const_minus_one(); }; template bool operator==( const Polynomial& f0 , const T& t1 ); template bool operator==( const Polynomial& f0 , const Polynomial& f1 ); template inline bool operator!=( const Polynomial& f0 , const P& f1 ); template inline Polynomial operator+( const Polynomial& f0 , const P& f1 ); template inline Polynomial operator-( const Polynomial& f ); template inline Polynomial operator-( const Polynomial& f0 , const P& f1 ); template inline Polynomial operator*( const Polynomial& f0 , const P& f1 ); template inline Polynomial operator/( const Polynomial& f0 , const T& t1 ); template inline Polynomial operator/( const Polynomial& f0 , const Polynomial& f1 ); template inline Polynomial operator%( const Polynomial& f0 , const P& f1 ); template inline Polynomial operator<<( const Polynomial& f , const T& t ); // 多項式などの列の総乗を分割統治で計算し、その結果を第1成分に格納して参照返しする。 // Vはeraseを持つ必要がある。 template typename V> T& Prod( V& f ); #define DEFINITION_BODY_OF_PARTIAL_SPECIALISATION_OF_MULTIPLICATION_OF_POLYNOMIAL_PROTH_MOD( TYPE , ARG , RHS ) \ template <> \ Polynomial& Polynomial::operator*=( ARG f ) \ { \ \ if( m_size != 0 ){ \ \ vector v{}; \ v.swap( m_f ); \ TruncatedPolynomial this_copy{ m_size + f.m_size - 1 , move( v ) }; \ this_copy *= RHS; \ m_f = move( this_copy.Polynomial::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( 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::m_size < N_OUTPUT_LIM ){ \ \ for( uint i = Polynomial::m_size ; i < N_OUTPUT_LIM ; i++ ){ \ \ Polynomial::m_f.push_back( 0 ); \ \ } \ \ Polynomial::m_size = N_OUTPUT_LIM; \ \ } \ #define SET_VECTOR_FOR_ANSWER_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL( N_OUTPUT_LIM ) \ vector 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::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::m_f[j] * f.Polynomial::m_f[i - j]; \ \ } \ \ Polynomial::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::m_f[j] * f.Polynomial::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::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::m_size == 0 ); \ uint N_output_max = Polynomial::m_size + f.Polynomial::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::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::m_f , Polynomial::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::m_size , N_input_start_1 ); \ \ #define SET_N_INPUT_RANGE \ SET_N_INPUT_MAX_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( Polynomial::m_f , Polynomial::m_size , N_input_max_0 ); \ SET_N_INPUT_MAX_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( f , f.Polynomial::m_size < m_N ? f.Polynomial::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 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; \ const T& zero = Polynomial::const_zero(); \ bool searching = true; \ \ if( Polynomial::m_size < border_0 && f.Polynomial::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 class TruncatedPolynomial; template TruncatedPolynomial Differential( const uint& n , const TruncatedPolynomial& f ); template TruncatedPolynomial TruncatedDifferential( const TruncatedPolynomial& f , const uint& N_output_start_plus_one ); template TruncatedPolynomial TruncatedIntegral( const TruncatedPolynomial& f , const uint& N_output_start ); template class TruncatedPolynomial : public Polynomial { friend TruncatedPolynomial Differential( const uint& n , const TruncatedPolynomial& f ); friend TruncatedPolynomial TruncatedDifferential( const TruncatedPolynomial& f , const uint& N_output_start_plus_one ); friend TruncatedPolynomial TruncatedIntegral( const TruncatedPolynomial& 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& f ); inline TruncatedPolynomial( TruncatedPolynomial&& f ); inline TruncatedPolynomial( const uint& N , const T& t ); inline TruncatedPolynomial( const uint& N , const Polynomial& f ); inline TruncatedPolynomial( const uint& N , Polynomial&& f ); inline TruncatedPolynomial( const uint& N , const uint& i , const T& t ); inline TruncatedPolynomial( const uint& N , const uint& i , T&& t ); template inline TruncatedPolynomial( const uint& N , const uint& i , const Arg& t ); inline TruncatedPolynomial( const uint& N , vector&& f ); // m_Nも代入されることに注意 inline TruncatedPolynomial& operator=( const TruncatedPolynomial& f ); inline TruncatedPolynomial& operator=( TruncatedPolynomial&& f ); inline TruncatedPolynomial& operator=( const T& t ); inline TruncatedPolynomial& operator=( T&& t ); template inline TruncatedPolynomial& operator=( const Arg& n ); inline TruncatedPolynomial& operator=( const Polynomial& f ); inline TruncatedPolynomial& operator=( Polynomial&& f ); // m_Nは変化しないことに注意 inline TruncatedPolynomial& operator+=( const T& t ); inline TruncatedPolynomial& operator+=( const Polynomial& f ); // m_N == 0の時のみm_Nが変化する。（内積などの計算の仕様） inline TruncatedPolynomial& operator+=( const TruncatedPolynomial& 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& TruncatedPlus( const Polynomial& f , const uint& N_input_start , const uint& N_input_limit ); // m_Nは変化しないことに注意 inline TruncatedPolynomial& operator-=( const T& t ); inline TruncatedPolynomial& operator-=( const Polynomial& f ); // m_N == 0の時のみm_Nが変化する。 inline TruncatedPolynomial& operator-=( const TruncatedPolynomial& 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& TruncatedMinus( const Polynomial& f , const uint& N_input_start , const uint& N_input_limit ); inline TruncatedPolynomial& operator*=( const T& t ); // m_N > 0の場合のみサポート。 TruncatedPolynomial& operator*=( const Polynomial& f ); inline TruncatedPolynomial& operator*=( Polynomial&& 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& TruncatedMultiplication( const Polynomial& 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 TruncatedMultiplication_const( const Polynomial& f , const uint& N_output_start , const uint& N_output_lim ) const; inline TruncatedPolynomial& operator/=( const T& t ); // Polynomialとしての商でないことに注意。 inline TruncatedPolynomial& operator/=( const TruncatedPolynomial& t ); inline TruncatedPolynomial& operator%=( const T& t ); inline TruncatedPolynomial operator-() const; // 合成 inline TruncatedPolynomial operator()( const TruncatedPolynomial& f ) const; inline void SetTruncation( const uint& N ) noexcept; inline const uint& GetTruncation() const noexcept; // N次未満を0に変更。 inline TruncatedPolynomial& TruncateInitial( const uint& N ) noexcept; // N次以上を0に変更。 inline TruncatedPolynomial& TruncateFinal( const uint& N ) noexcept; }; template inline constexpr const uint Multiplication_border_0 = 17; template inline TruncatedPolynomial operator+( const TruncatedPolynomial& f0 , const P& f1 ); template inline TruncatedPolynomial operator-( const TruncatedPolynomial& f ); template inline TruncatedPolynomial operator-( const TruncatedPolynomial& f0 , const P& f1 ); template inline TruncatedPolynomial operator*( const TruncatedPolynomial& f0 , const P& f1 ); template inline TruncatedPolynomial operator/( const TruncatedPolynomial& f0 , const P& f1 ); template inline TruncatedPolynomial operator%( const TruncatedPolynomial& f0 , const T& t1 ); // m_Nが1下がることに注意。 template inline TruncatedPolynomial Differential( const TruncatedPolynomial& f ); // m_Nがn下がることに注意。 template inline TruncatedPolynomial Differential( const uint& n , const TruncatedPolynomial& f ); // m_Nが1下がることに注意。 // N_output_start_plus_one > 0の場合のみサポート。 template TruncatedPolynomial TruncatedDifferential( const TruncatedPolynomial& f , const uint& N_output_start_plus_one ); // m_Nが1上がることに注意。 // Tが標数0またはf.m_N + 1以上の体の場合のみサポート。 template inline TruncatedPolynomial Integral( const TruncatedPolynomial& f ); // m_Nが1上がることに注意。 // N_output_start > 0の場合のみサポート。 template TruncatedPolynomial TruncatedIntegral( const TruncatedPolynomial& f , const uint& N_output_start ); // f[0]が可逆な場合のみサポート。 template TruncatedPolynomial Inverse( const TruncatedPolynomial& f ); // Tが標数0またはf.m_N以上の体でかつf[0] == 0の場合のみサポート。 template TruncatedPolynomial Exp( const TruncatedPolynomial& f ); // Tが標数0またはf.m_N以上の体でかつf[0] == 1の場合のみサポート。 template inline TruncatedPolynomial Log( const TruncatedPolynomial& f ); // Tが標数0またはf.m_N以上の体でかつf[0] == 1の場合のみサポート。 template TruncatedPolynomial Power( const TruncatedPolynomial& f , const T& t ); template inline TruncatedPolynomial::TruncatedPolynomial( const uint& N ) : Polynomial() , m_N( N ) { Polynomial::m_f.reserve( m_N ); } template inline TruncatedPolynomial::TruncatedPolynomial( const TruncatedPolynomial& f ) : Polynomial( f ) , m_N( f.m_N ) { Polynomial::m_f.reserve( m_N ); } template inline TruncatedPolynomial::TruncatedPolynomial( TruncatedPolynomial&& f ) : Polynomial( move( f ) ) , m_N( move( f.m_N ) ) { Polynomial::m_f.reserve( m_N ); } template inline TruncatedPolynomial::TruncatedPolynomial( const uint& N , const T& t ) : Polynomial( t ) , m_N( N ) { Polynomial::m_f.reserve( m_N ); } template inline TruncatedPolynomial::TruncatedPolynomial( const uint& N , const Polynomial& f ) : Polynomial() , m_N( N ) { Polynomial::m_size = f.Polynomial::m_size < m_N ? f.Polynomial::m_size : m_N; Polynomial::m_f = vector( Polynomial::m_size ); for( uint i = 0 ; i < Polynomial::m_size ; i++ ){ Polynomial::m_f[i] = f.Polynomial::m_f[i]; } Polynomial::m_f.reserve( m_N ); } template inline TruncatedPolynomial::TruncatedPolynomial( const uint& N , Polynomial&& f ) : Polynomial() , m_N( N ) { if( f.Polynomial::m_size < m_N * 2 ){ Polynomial::operator=( move( f ) ); if( f.Polynomial::m_size < m_N ){ Polynomial::m_f.reserve( m_N ); } else { TruncateFinal( m_N ); } } else { Polynomial::m_f = vector( m_N ); for( uint i = 0 ; i < m_N ; i++ ){ Polynomial::m_f[i] = move( f.Polynomial::m_f[i] ); } Polynomial::m_size = m_N; } } template inline TruncatedPolynomial::TruncatedPolynomial( const uint& N , const uint& i , const T& t ) : Polynomial() , m_N( N ) { if( i < m_N ? t != Polynomial::const_zero() : false ){ Polynomial::operator[]( i ) = t; } Polynomial::m_f.reserve( m_N ); } template inline TruncatedPolynomial::TruncatedPolynomial( const uint& N , const uint& i , T&& t ) : Polynomial() , m_N( N ) { if( i < m_N ? t != Polynomial::const_zero() : false ){ Polynomial::operator[]( i ) = move( t ); } Polynomial::m_f.reserve( m_N ); } template template inline TruncatedPolynomial::TruncatedPolynomial( const uint& N , const uint& i , const Arg& n ) : TruncatedPolynomial( N , i , T( n ) ) {} template inline TruncatedPolynomial::TruncatedPolynomial( const uint& N , vector&& f ) : Polynomial() , m_N( N ) { const uint f_size = f.size(); if( f_size < m_N * 2 ){ Polynomial::operator=( move( f ) ); if( f_size < m_N ){ Polynomial::m_f.reserve( m_N ); } else { TruncateFinal( m_N ); } } else { Polynomial::m_f = vector( m_N ); for( uint i = 0 ; i < m_N ; i++ ){ Polynomial::m_f[i] = move( f[i] ); } Polynomial::m_f.reserve( m_N ); } } template inline TruncatedPolynomial& TruncatedPolynomial::operator=( const TruncatedPolynomial& f ) { Polynomial::operator=( f ); m_N = f.m_N; Polynomial::m_f.reserve( m_N ); return *this; } template inline TruncatedPolynomial& TruncatedPolynomial::operator=( TruncatedPolynomial&& f ) { Polynomial::operator=( move( f ) ); m_N = move( f.m_N ); Polynomial::m_f.reserve( m_N ); return *this; } template inline TruncatedPolynomial& TruncatedPolynomial::operator=( const T& t ) { Polynomial::operator=( t ); return *this; } template inline TruncatedPolynomial& TruncatedPolynomial::operator=( T&& t ) { Polynomial::operator=( move( t ) ); return *this; } template template inline TruncatedPolynomial& TruncatedPolynomial::operator=( const Arg& n ) { Polynomial::operator=( T( n ) ); return *this; } template inline TruncatedPolynomial& TruncatedPolynomial::operator=( const Polynomial& f ) { return operator=( TruncatedPolynomial( m_N , f ) ); } template inline TruncatedPolynomial& TruncatedPolynomial::operator=( Polynomial&& f ) { return operator=( TruncatedPolynomial( m_N , move( f ) ) ); } template inline TruncatedPolynomial& TruncatedPolynomial::operator+=( const T& t ) { Polynomial::operator+=( t ); return *this; } template inline TruncatedPolynomial& TruncatedPolynomial::operator+=( const Polynomial& f ) { return TruncatedPolynomial::TruncatedPlus( f , 0 , f.m_size ); } template inline TruncatedPolynomial& TruncatedPolynomial::operator+=( const TruncatedPolynomial& f ) { return m_N == 0 ? operator=( f ) : TruncatedPolynomial::TruncatedPlus( f , 0 , f.Polynomial::m_size ); } template TruncatedPolynomial& TruncatedPolynomial::TruncatedPlus( const Polynomial& f , const uint& N_input_start , const uint& N_input_lim ) { const uint& size = N_input_lim < m_N ? N_input_lim < f.Polynomial::m_size ? N_input_lim : f.Polynomial::m_size : m_N < f.Polynomial::m_size ? m_N : f.Polynomial::m_size; if( Polynomial::m_size < size ){ Polynomial::m_f.reserve( size ); for( uint i = N_input_start ; i < Polynomial::m_size ; i++ ){ Polynomial::m_f[i] += f.Polynomial::m_f[i]; } for( uint i = Polynomial::m_size ; i < size ; i++ ){ Polynomial::m_f.push_back( f.Polynomial::m_f[i] ); } Polynomial::m_size = size; } else { for( uint i = N_input_start ; i < size ; i++ ){ Polynomial::m_f[i] += f.Polynomial::m_f[i]; } } return *this; } template inline TruncatedPolynomial& TruncatedPolynomial::operator-=( const T& t ) { Polynomial::operator-=( t ); return *this; } template