#796950 (C++17) No.2062 Sum of Subset mod 999630629

提出ソース

結果

問題	No.2062 Sum of Subset mod 999630629
ユーザー	👑 p-adic
提出日時	2022-09-14 01:30:56
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	4,561 ms / 5,000 ms
コード長	54,663 bytes
コンパイル時間	3,081 ms
コンパイル使用メモリ	234,176 KB
実行使用メモリ	151,260 KB
最終ジャッジ日時	2024-05-08 07:32:03
合計ジャッジ時間	37,760 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	10 ms 5,376 KB
testcase_09	AC	8 ms 5,376 KB
testcase_10	AC	8 ms 5,376 KB
testcase_11	AC	728 ms 40,492 KB
testcase_12	AC	723 ms 40,960 KB
testcase_13	AC	253 ms 22,404 KB
testcase_14	AC	716 ms 40,836 KB
testcase_15	AC	45 ms 6,676 KB
testcase_16	AC	1,093 ms 40,140 KB
testcase_17	AC	716 ms 40,416 KB
testcase_18	AC	255 ms 22,400 KB
testcase_19	AC	81 ms 8,628 KB
testcase_20	AC	207 ms 13,228 KB
testcase_21	AC	460 ms 22,116 KB
testcase_22	AC	240 ms 13,260 KB
testcase_23	AC	7 ms 5,376 KB
testcase_24	AC	7 ms 5,376 KB
testcase_25	AC	4,521 ms 149,692 KB
testcase_26	AC	4,500 ms 151,260 KB
testcase_27	AC	4,514 ms 149,692 KB
testcase_28	AC	4,561 ms 149,556 KB
testcase_29	AC	4,514 ms 149,812 KB
testcase_30	AC	2,168 ms 79,380 KB
testcase_31	AC	2,533 ms 78,256 KB

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

コンパイルメッセージ

main.cpp: In member function 'TrPo<T> TrPo<T>::FFT_TrMultiplication_const(const Po<T>&, uint, uint) const [with T = Mod<998244353>]':
main.cpp:27:384: warning: 'N_input_start_1' may be used uninitialized [-Wmaybe-uninitialized]
   27 | #define DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION ) SET_N_INPUT_START_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( Po<T>::m_f , Po<T>::m_size , N_input_start_0 ); CONNECT( CONNECT( RETURN_ZERO_FOR_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL_IF )( searching ); searching = true; SET_N_INPUT_START_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( f , f.Po<T>::m_size , N_input_start_1 );
      |                                                                                                                                                                                                                                                                                                                                                                                                ^~~~~~~~~~~~~~~
main.cpp:27:384: note: 'N_input_start_1' was declared here
   27 | #define DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION ) SET_N_INPUT_START_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( Po<T>::m_f , Po<T>::m_size , N_input_start_0 ); CONNECT( CONNECT( RETURN_ZERO_FOR_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL_IF )( searching ); searching = true; SET_N_INPUT_START_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( f , f.Po<T>::m_size , N_input_start_1 );
      |                                                                                                                                                                                                                                                                                                                                                                                                ^~~~~~~~~~~~~~~
main.cpp:18:108: note: in definition of macro 'SET_N_INPUT_START_FOR_MULTIPLICA

ソースコード

raw source code

#define CONST_INT_REF INT 
#define CONST_UINT_REF uint
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define TE template
#define TY typename
#define IN inline
#define OP operator
#define CO const
#define RE return
#define NE noexcept
#define VE vector
#define RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( CONDITION ) if( CONDITION ){ RE OP=( zero ); }
#define RETURN_ZERO_FOR_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL_IF( CONDITION ) if( CONDITION ){ RE TrPo<T>( m_N ); }
#define SET_VECTOR_FOR_ANSWER_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( N_OUTPUT_LIM ) if( Po<T>::m_size < N_OUTPUT_LIM ){ for( uint i = Po<T>::m_size ; i < N_OUTPUT_LIM ; i++ ){ Po<T>::m_f.push_back( 0 ); } Po<T>::m_size = N_OUTPUT_LIM; }
#define SET_VECTOR_FOR_ANSWER_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL( N_OUTPUT_LIM ) VE<T> answer( N_OUTPUT_LIM )
#define SET_SUM_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL Po<T>::m_f[i] = sum
#define SET_SUM_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL answer[i] = sum
#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 ) CO 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 += Po<T>::m_f[j] * f.Po<T>::m_f[i - j]; } Po<T>::m_f[i] = sum;
#define CONVOLUTION_FOR_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL( J_MIN ) CO 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 += Po<T>::m_f[j] * f.Po<T>::m_f[i - j]; }
#define SUBSTITUTE_CONNECT( S1 , S2 ) S1 ## S2 
#define CONNECT( S1 , S2 ) SUBSTITUTE_CONNECT( S1 , S2 ) 
#define DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION , ACCESS_ENTRY ) CONNECT( CONNECT( RETURN_ZERO_FOR_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL_IF )( Po<T>::m_size == 0 ); uint N_output_max = Po<T>::m_size + f.Po<T>::m_size - 2; if( N_output_max >= m_N ){ N_output_max = m_N - 1; } CO uint N_output_lim = N_output_max + 1; CONNECT( CONNECT( SET_VECTOR_FOR_ANSWER_OF_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL )( 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.Po<T>::OP[]( i - j ); } CONNECT( CONNECT( SET_SUM_OF_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL ); searching = i > 0; } 
#define DEFINITION_0_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION , Po<T>::m_f[j] ) 
#define DEFINITION_0_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MULTIPLICATION_CONST , Po<T>::OP[]( j ) ) 
#define DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION ) SET_N_INPUT_START_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( Po<T>::m_f , Po<T>::m_size , N_input_start_0 ); CONNECT( CONNECT( RETURN_ZERO_FOR_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL_IF )( searching ); searching = true; SET_N_INPUT_START_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( f , f.Po<T>::m_size , N_input_start_1 ); 
#define DEFINITION_1_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION )
#define DEFINITION_1_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MULTIPLICATION_CONST ) 
#define DEFINITION_2_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL SET_N_INPUT_MAX_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( Po<T>::m_f , Po<T>::m_size , N_input_max_0 ); SET_N_INPUT_MAX_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( f , f.Po<T>::m_size < m_N ? f.Po<T>::m_size : m_N , N_input_max_1 ); CO uint N_input_max_0_max_1 = N_input_max_0 + N_input_max_1; CO uint N_input_start_0_start_1 = N_input_start_0 + N_input_start_1; 
#define DEFINITION_2_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL DEFINITION_2_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL
#define DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION ) CO uint N_input_start_0_max_1 = N_input_start_0 + N_input_max_1; CO uint N_input_max_0_start_1 = N_input_max_0 + N_input_start_1; CO uint N_output_max_fixed = N_output_lim_fixed - 1; CONNECT( CONNECT( SET_VECTOR_FOR_ANSWER_OF_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL )( N_output_lim_fixed ); for( uint i = N_output_max_fixed ; i > N_input_start_0_max_1 ; i-- ){ CONNECT( CONNECT( CONVOLUTION_FOR_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL )( 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-- ){ CONNECT( CONNECT( CONVOLUTION_FOR_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL )( N_input_start_0 ); searching = i > N_input_start_0_start_1; }
#define DEFINITION_3_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION ) 
#define DEFINITION_3_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MULTIPLICATION_CONST ) 
#define DEFINITION_4_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL uint two_power = FFT_Multiplication_border_1_2<T>; uint exponent = FFT_Multiplication_border_1_2_exponent<T>; T two_power_inv{ FFT_Multiplication_border_1_2_inv<T> }; while( N_input_truncated_deg_0_deg_1 >= two_power ){ two_power *= 2; two_power_inv /= 2; exponent++; } VE<T> f0{ move( FFT<T>( Po<T>::m_f , N_input_start_0 , N_input_max_0 + 1 , 0 , two_power , exponent ) ) }; CO VE<T> f1{ move( FFT<T>( f.Po<T>::m_f , N_input_start_1 , N_input_max_1 + 1 , 0 , two_power , exponent ) ) }; for( uint i = 0 ; i < two_power ; i++ ){ f0[i] *= f1[i]; } 
#define DEFINITION_4_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL DEFINITION_4_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL 
#define DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( TYPE , RECURSION ) CO uint& N = f.GetTruncation(); uint power; uint power_2 = 1; TrPo< TYPE > f_inv{ power_2 , Po< 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 ); RE f_inv
#define DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( TYPE , RECURSION ) CO uint& N = f.GetTruncation(); uint power; uint power_2 = 1; TrPo< TYPE > f_exp{ power_2 , Po< TYPE >::const_one() }; while( power_2 < N ){ power = power_2; power_2 *= 2; f_exp.SetTruncation( power_2 ); RECURSION; } f_exp.SetTruncation( N ); RE f_exp
#define DEFINITION_OF_PARTIAL_SPECIALISATION_OF_MULTIPLICATION_OF_TRUNCATED_POLYNOMIAL( TYPE , BORDER_0 , BORDER_1 , BORDER_1_2 , BORDER_1_2_EXPONENT , BORDER_1_2_INV ) TE <> constexpr CO uint FFT_Multiplication_border_0< TYPE > = BORDER_0; TE <> constexpr CO uint FFT_Multiplication_border_1< TYPE > = BORDER_1; TE <> constexpr CO uint FFT_Multiplication_border_1_2< TYPE > = BORDER_1_2; TE <> constexpr CO uint FFT_Multiplication_border_1_2_exponent< TYPE > = BORDER_1_2_EXPONENT; TE <> constexpr CO uint FFT_Multiplication_border_1_2_inv< TYPE > = BORDER_1_2_INV; TE <> IN TrPo< TYPE >& TrPo< TYPE >::OP*=( CO Po< TYPE >& f ) { RE TrPo< TYPE >::FFT_Multiplication( f ); } TE <> TrPo< TYPE > Inverse( CO TrPo< TYPE >& f ) { DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( TYPE , f_inv.TrMinus( f_inv.FFT_TrMultiplication_const( f , power , power_2 ).FFT_TrMultiplication( f_inv , power , power_2 ) , power , power_2 ) ); } TE <> TrPo< TYPE > Exp( CO TrPo< TYPE >& f ) { DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( TYPE , f_exp.TrMinus( ( TrIntegral( Differential( f_exp ).FFT_TrMultiplication_const( Inverse( f_exp ) , power - 1 , power_2 ) , power ).TrMinus( f , power , power_2 ) ).FFT_TrMultiplication( f_exp , power , power_2 ) , power , power_2 ) ); }
#define MOD Mod<P>
#include<bits/stdc++.h>
using namespace std;using uint = unsigned int;using ll = long long;constexpr CO ll P = 998244353; constexpr CO ll Q = 999630629;
TE <TY INT> INT Residue( CONST_INT_REF M , CONST_INT_REF n ) NE; TE <TY INT> INT Residue( CONST_INT_REF M , CONST_INT_REF n ) NE { if( M == 0 ){ RE 0; } CO INT M_abs = ( M > 0 ? M : -M ); if( n < 0 ){ CO INT n_abs = -n; CO INT res = n_abs % M_abs; RE res == 0 ? res : M_abs - res; } RE n % M_abs; } TE <TY T> using VLArray = list<T>; using INT_TYPE_FOR_MOD = long long int; TE <INT_TYPE_FOR_MOD M> class Mod { protected: INT_TYPE_FOR_MOD m_n; INT_TYPE_FOR_MOD m_inv; public: IN Mod() NE; IN Mod( CO INT_TYPE_FOR_MOD& n ) NE; IN Mod( CO Mod<M>& n ) NE; IN Mod<M>& OP=( CO INT_TYPE_FOR_MOD& n ) NE; Mod<M>& OP=( CO Mod<M>& n ) NE; Mod<M>& OP+=( CO INT_TYPE_FOR_MOD& n ) NE; IN Mod<M>& OP+=( CO Mod<M>& n ) NE; IN Mod<M>& OP-=( CO INT_TYPE_FOR_MOD& n ) NE; IN Mod<M>& OP-=( CO Mod<M>& n ) NE; Mod<M>& OP*=( CO INT_TYPE_FOR_MOD& n ) NE; Mod<M>& OP*=( CO Mod<M>& n ) NE; virtual Mod<M>& OP/=( CO INT_TYPE_FOR_MOD& n ); virtual Mod<M>& OP/=( CO Mod<M>& n ); Mod<M>& OP%=( CO INT_TYPE_FOR_MOD& n ); IN Mod<M>& OP%=( CO Mod<M>& n ); IN Mod<M> OP-() CO NE; IN Mod<M>& OP++() NE; IN Mod<M>& OP++( int ) NE; IN Mod<M>& OP--() NE; IN Mod<M>& OP--( int ) NE; IN CO INT_TYPE_FOR_MOD& Represent() CO NE; void Invert() NE; bool CheckInvertible() NE; bool IsSmallerThan( CO INT_TYPE_FOR_MOD& n ) CO NE; bool IsBiggerThan( CO INT_TYPE_FOR_MOD& n ) CO NE; }; TE <INT_TYPE_FOR_MOD M> IN bool OP==( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP==( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP==( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP==( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP!=( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP!=( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP!=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP!=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP<( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP<( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP<( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP<=( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP<=( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP<=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP<=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP>( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP>( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP>( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP>( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP>=( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP>=( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP>=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN bool OP>=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> Mod<M> OP+( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE <INT_TYPE_FOR_MOD M> Mod<M> OP+( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> Mod<M> OP+( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP-( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE <INT_TYPE_FOR_MOD M> Mod<M> OP-( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> Mod<M> OP-( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> Mod<M> OP*( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE <INT_TYPE_FOR_MOD M> Mod<M> OP*( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> Mod<M> OP*( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE; TE <INT_TYPE_FOR_MOD M> Mod<M> OP/( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ); TE <INT_TYPE_FOR_MOD M> Mod<M> OP/( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ); TE <INT_TYPE_FOR_MOD M> Mod<M> OP/( CO Mod<M>& n0 , CO Mod<M>& n1 ); TE <INT_TYPE_FOR_MOD M> Mod<M> OP%( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ); TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP%( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ); TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP%( CO Mod<M>& n0 , CO Mod<M>& n1 ); TE <INT_TYPE_FOR_MOD M> Mod<M> Inverse( CO Mod<M>& n ); TE <INT_TYPE_FOR_MOD M> Mod<M> Power( CO Mod<M>& n , CO INT_TYPE_FOR_MOD& p , CO string& method = "normal" ); TE <> IN Mod<2> Power( CO Mod<2>& n , CO INT_TYPE_FOR_MOD& p , CO string& method ); TE <INT_TYPE_FOR_MOD M> IN Mod<M> Power( CO Mod<M>& n , CO Mod<M>& p , CO string& method = "normal" ); TE <> IN Mod<2> Power( CO Mod<2>& n , CO Mod<2>& p , CO string& method ); TE <TY T> IN T Square( CO T& t ); TE <> IN Mod<2> Square<Mod<2> >( CO Mod<2>& t ); TE <INT_TYPE_FOR_MOD M> IN string to_string( CO Mod<M>& n ) NE; void LazyEvaluationOfModularInverse( CO INT_TYPE_FOR_MOD& M , CO INT_TYPE_FOR_MOD& n , INT_TYPE_FOR_MOD& m ); TE <INT_TYPE_FOR_MOD M> IN Mod<M>::Mod() NE : m_n( 0 ) , m_inv( M ){} TE <INT_TYPE_FOR_MOD M> IN Mod<M>::Mod( CO INT_TYPE_FOR_MOD& n ) NE : m_n( Residue<INT_TYPE_FOR_MOD>( M , n ) ) , m_inv( 0 ){} TE <INT_TYPE_FOR_MOD M> IN Mod<M>::Mod( CO Mod<M>& n ) NE : m_n( n.m_n ) , m_inv( 0 ){} TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP=( CO INT_TYPE_FOR_MOD& n ) NE { RE OP=( Mod<M>( n ) ); } TE <INT_TYPE_FOR_MOD M> Mod<M>& Mod<M>::OP=( CO Mod<M>& n ) NE { m_n = n.m_n; m_inv = n.m_inv; RE *this; } TE <INT_TYPE_FOR_MOD M> Mod<M>& Mod<M>::OP+=( CO INT_TYPE_FOR_MOD& n ) NE { m_n = Residue<INT_TYPE_FOR_MOD>( M , m_n + n ); m_inv = 0; RE *this; } TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP+=( CO Mod<M>& n ) NE { RE OP+=( n.m_n ); }; TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP-=( CO INT_TYPE_FOR_MOD& n ) NE { RE OP+=( -n ); } TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP-=( CO Mod<M>& n ) NE { RE OP-=( n.m_n ); } TE <INT_TYPE_FOR_MOD M> Mod<M>& Mod<M>::OP*=( CO INT_TYPE_FOR_MOD& n ) NE { m_n = Residue<INT_TYPE_FOR_MOD>( M , m_n * n ); m_inv = 0; RE *this; } TE <INT_TYPE_FOR_MOD M> Mod<M>& Mod<M>::OP*=( CO Mod<M>& n ) NE { m_n = Residue<INT_TYPE_FOR_MOD>( M , m_n * n.m_n ); if( m_inv == 0 || n.m_inv == 0 ){ m_inv = 0; } else if( m_inv == M || n.m_inv == M ){ m_inv = M; } else { Residue<INT_TYPE_FOR_MOD>( M , m_inv * n.m_inv ); } RE *this; } TE <INT_TYPE_FOR_MOD M> Mod<M>& Mod<M>::OP/=( CO INT_TYPE_FOR_MOD& n ) { RE OP/=( Mod<M>( n ) ); } TE <INT_TYPE_FOR_MOD M> Mod<M>& Mod<M>::OP/=( CO Mod<M>& n ) { RE OP*=( Inverse( n ) ); } TE <INT_TYPE_FOR_MOD M> Mod<M>& Mod<M>::OP%=( CO INT_TYPE_FOR_MOD& n ) { m_n %= Residue<INT_TYPE_FOR_MOD>( M , n ); m_inv = 0; RE *this; } TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP%=( CO Mod<M>& n ) { RE OP%=( n.m_n ); } TE <INT_TYPE_FOR_MOD M> IN Mod<M> Mod<M>::OP-() CO NE { RE Mod<M>( 0 ).OP-=( *this ); } TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP++() NE { RE OP+=( 1 ); } TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP++( int ) NE { RE OP++(); } TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP--() NE { RE OP-=( 1 ); } TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP--( int ) NE { RE OP-=(); } TE <INT_TYPE_FOR_MOD M> IN CO INT_TYPE_FOR_MOD& Mod<M>::Represent() CO NE { RE m_n; } TE <INT_TYPE_FOR_MOD M> void Mod<M>::Invert() NE { if( CheckInvertible() ){ INT_TYPE_FOR_MOD i = m_inv; m_inv = m_n; m_n = i; } else { m_n = M; m_inv = M; } RE; } TE <INT_TYPE_FOR_MOD M> bool Mod<M>::CheckInvertible() NE { if( m_inv == 0 ){ LazyEvaluationOfModularInverse( M , m_n , m_inv ); } RE m_inv != M; } TE <INT_TYPE_FOR_MOD M> IN bool Mod<M>::IsSmallerThan( CO INT_TYPE_FOR_MOD& n ) CO NE { RE m_n < Residue<INT_TYPE_FOR_MOD>( M , n ); } TE <INT_TYPE_FOR_MOD M> IN bool Mod<M>::IsBiggerThan( CO INT_TYPE_FOR_MOD& n ) CO NE { RE m_n > Residue<INT_TYPE_FOR_MOD>( M , n ); } TE <INT_TYPE_FOR_MOD M> IN bool OP==( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { RE n0 == Mod<M>( n1 ); } TE <INT_TYPE_FOR_MOD M> IN bool OP==( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE Mod<M>( n0 ) == n0; } TE <INT_TYPE_FOR_MOD M> IN bool OP==( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE n0.Represent() == n1.Represent(); } TE <INT_TYPE_FOR_MOD M> IN bool OP!=( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { RE !( n0 == n1 ); } TE <INT_TYPE_FOR_MOD M> IN bool OP!=( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE !( n0 == n1 ); } TE <INT_TYPE_FOR_MOD M> IN bool OP!=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE !( n0 == n1 ); } TE <INT_TYPE_FOR_MOD M> IN bool OP<( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { RE n0.IsSmallerThan( n1 ); } TE <INT_TYPE_FOR_MOD M> IN bool OP<( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE n1.IsBiggerThan( n0 ); } TE <INT_TYPE_FOR_MOD M> IN bool OP<( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE n0.Represent() < n1.Represent(); } TE <INT_TYPE_FOR_MOD M> IN bool OP<=( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { RE !( n1 < n0 ); } TE <INT_TYPE_FOR_MOD M> IN bool OP<=( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE !( n1 < n0 ); } TE <INT_TYPE_FOR_MOD M> IN bool OP<=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE !( n1 < n0 ); } TE <INT_TYPE_FOR_MOD M> IN bool OP>( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { RE n1 < n0; } TE <INT_TYPE_FOR_MOD M> IN bool OP>( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE n1 < n0; } TE <INT_TYPE_FOR_MOD M> IN bool OP>( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE n1 < n0; } TE <INT_TYPE_FOR_MOD M> IN bool OP>=( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { RE !( n0 < n1 ); } TE <INT_TYPE_FOR_MOD M> IN bool OP>=( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE !( n0 < n1 ); } TE <INT_TYPE_FOR_MOD M> IN bool OP>=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE !( n0 < n1 ); } TE <INT_TYPE_FOR_MOD M> Mod<M> OP+( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { auto n = n0; n += n1; RE n; } TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP+( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE n1 + n0; } TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP+( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE n0 + n1.Represent(); } TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP-( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { RE n0 + ( -n1 ); } TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP-( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE Mod<M>( n0 - n1.Represent() ); } TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP-( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE n0 - n1.Represent(); } TE <INT_TYPE_FOR_MOD M> Mod<M> OP*( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { auto n = n0; n *= n1; RE n; } TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP*( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE n1 * n0; } TE <INT_TYPE_FOR_MOD M> Mod<M> OP*( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { auto n = n0; n *= n1; RE n; } TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP/( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) { RE n0 / Mod<M>( n1 ); } TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP/( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) { RE Mod<M>( n0 ) / n1; } TE <INT_TYPE_FOR_MOD M> Mod<M> OP/( CO Mod<M>& n0 , CO Mod<M>& n1 ) { auto n = n0; n /= n1; RE n; } TE <INT_TYPE_FOR_MOD M> Mod<M> OP%( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) { auto n = n0; n %= n1; RE n; } TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP%( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) { RE Mod<M>( n0 ) % n1.Represent(); } TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP%( CO Mod<M>& n0 , CO Mod<M>& n1 ) { RE n0 % n1.Represent(); } TE <INT_TYPE_FOR_MOD M> Mod<M> Inverse( CO Mod<M>& n ) { auto n_copy = n; n_copy.Invert(); RE n_copy; } TE <INT_TYPE_FOR_MOD M> Mod<M> Power( CO Mod<M>& n , CO INT_TYPE_FOR_MOD& p , CO string& method ) { if( p >= 0 ){ RE Power<Mod<M>,INT_TYPE_FOR_MOD>( n , p , 1 , true , true , method ); } RE Inverse( Power<M>( n , -p , method ) ); } TE <> IN Mod<2> Power( CO Mod<2>& n , CO INT_TYPE_FOR_MOD& p , CO string& method ) { RE p == 0 ? 1 : n; } TE <INT_TYPE_FOR_MOD M> IN Mod<M> Power( CO Mod<M>& n , CO Mod<M>& p , CO string& method ) { RE Power<Mod<M>,INT_TYPE_FOR_MOD>( n , p.Represent() , method ); } TE <> IN Mod<2> Power( CO Mod<2>& n , CO Mod<2>& p , CO string& method ) { RE p == 0 ? 1 : n; } TE <> IN Mod<2> Square<Mod<2> >( CO Mod<2>& t ) { RE t; } TE <INT_TYPE_FOR_MOD M> IN string to_string( CO Mod<M>& n ) NE { RE to_string( n.Represent() ) + " + MZ"; } void LazyEvaluationOfModularInverse( CO INT_TYPE_FOR_MOD& M , CO INT_TYPE_FOR_MOD& n , INT_TYPE_FOR_MOD& m ) { static VLArray<INT_TYPE_FOR_MOD> memory_M{}; static VLArray<VE<INT_TYPE_FOR_MOD> > memory_inverse{}; auto itr_M = memory_M.begin() , end_M = memory_M.end(); auto itr_inverse = memory_inverse.begin(); VE<INT_TYPE_FOR_MOD>* p_inverse = nullptr; while( itr_M != end_M && p_inverse == nullptr ){ if( *itr_M == M ){ p_inverse = &( *itr_inverse ); } itr_M++; itr_inverse++; } if( p_inverse == nullptr ){ memory_M.push_front( M ); memory_inverse.push_front( VE<INT_TYPE_FOR_MOD>() ); p_inverse = &( memory_inverse.front() ); p_inverse->push_back( M ); } CO INT_TYPE_FOR_MOD size = p_inverse->size(); for( INT_TYPE_FOR_MOD i = size ; i <= n ; i++ ){ p_inverse->push_back( 0 ); } INT_TYPE_FOR_MOD& n_inv = ( *p_inverse )[n]; if( n_inv != 0 ){ m = n_inv; RE; } CO INT_TYPE_FOR_MOD M_abs = M >= 0 ? M : -M; CO INT_TYPE_FOR_MOD n_sub = M_abs % n; INT_TYPE_FOR_MOD n_sub_inv = ( *p_inverse )[n_sub]; if( n_sub_inv == 0 ){ LazyEvaluationOfModularInverse( M , n_sub , n_sub_inv ); } if( n_sub_inv != M ){ n_inv = M_abs - ( ( n_sub_inv * ( M_abs / n ) ) % M_abs ); m = n_inv; RE; } for( INT_TYPE_FOR_MOD i = 1 ; i < M_abs ; i++ ){ if( ( n * i ) % M_abs == 1 ){ n_inv = i; m = n_inv; RE; } } n_inv = M; m = n_inv; RE; } TE <TY T> IN constexpr CO uint LimitOfPowerForFFT; TE <TY T> IN constexpr CO uint BorderForFFT; TE <TY T> IN CO T ( &PrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT<T>]; TE <TY T> IN CO T ( &InversePrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT<T>]; TE <TY T> IN VE<T> FFT( CO VE<T>& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF two_power , CONST_UINT_REF exponent ); TE <TY T> IN VE<T> FFT( CO VE<T>& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim , CONST_UINT_REF N_output_shift , CONST_UINT_REF two_power , CONST_UINT_REF exponent ); TE <TY T> VE<T> IFFT( CO VE<T>& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF two_power , CO T& two_power_inv , CONST_UINT_REF exponent ); TE <TY T> VE<T> IFFT( CO VE<T>& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim , CONST_UINT_REF N_output_shift , CONST_UINT_REF two_power , CO T& two_power_inv , CONST_UINT_REF exponent ); TE <> IN constexpr CO uint LimitOfPowerForFFT<MOD> = 24; TE <> IN constexpr CO uint BorderForFFT<MOD> = 4; TE <> IN CO MOD ( &PrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT<MOD>] { static CO MOD PRT[ LimitOfPowerForFFT<MOD> ] = { MOD( 1 ) , MOD( 998244352 ) , MOD( 911660635 ) , MOD( 625715529 ) , MOD( 373294451 ) , MOD( 827987769 ) , MOD( 280333251 ) , MOD( 581015842 ) , MOD( 628092333 ) , MOD( 300892551 ) , MOD( 586046298 ) , MOD( 615001099 ) , MOD( 318017948 ) , MOD( 64341522 ) , MOD( 106061068 ) , MOD( 304605202 ) , MOD( 631920086 ) , MOD( 857779016 ) , MOD( 841431251 ) , MOD( 805775211 ) , MOD( 390359979 ) , MOD( 923521 ) , MOD( 961 ) , MOD( 31 ) }; RE PRT; } TE <> IN CO MOD ( &InversePrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT<MOD>] { static CO MOD PRT[ LimitOfPowerForFFT<MOD> ] = { MOD( 1 ) , MOD( 998244352 ) , MOD( 86583718 ) , MOD( 488723995 ) , MOD( 369330050 ) , MOD( 543653592 ) , MOD( 382946991 ) , MOD( 844956623 ) , MOD( 91420391 ) , MOD( 433414612 ) , MOD( 288894979 ) , MOD( 260490556 ) , MOD( 857007890 ) , MOD( 736054570 ) , MOD( 474649464 ) , MOD( 948509906 ) , MOD( 114942468 ) , MOD( 962405921 ) , MOD( 667573957 ) , MOD( 46809892 ) , MOD( 304321983 ) , MOD( 30429817 ) , MOD( 293967900 ) , MOD( 128805723 ) }; RE PRT; } TE <TY T> static VE<T> FFT_Body( CO VE<T>& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim , CONST_UINT_REF N_output_shift , CONST_UINT_REF two_power , CONST_UINT_REF exponent , CO T ( &PRT )[LimitOfPowerForFFT<T>] ); TE <TY T> static VE<T> FFT_Body( CO VE<T>& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF two_power , CONST_UINT_REF exponent , CONST_UINT_REF start , CONST_UINT_REF depth , CO T ( &PRT )[LimitOfPowerForFFT<T>] ); TE <TY T> IN VE<T> FFT( CO VE<T>& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF two_power , CONST_UINT_REF exponent ) { RE FFT_Body<T>( f , N_input_start , N_input_lim , N_input_shift , two_power , exponent , 0 , 1 , PrimitiveRootOfTwoForFFT<T>() ); } TE <TY T> IN VE<T> FFT( CO VE<T>& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim , CONST_UINT_REF N_output_shift , CONST_UINT_REF two_power , CONST_UINT_REF exponent ) { RE FFT_Body<T>( f , N_input_start , N_input_lim , N_input_shift , N_output_start , N_output_lim , N_output_shift , two_power , exponent , PrimitiveRootOfTwoForFFT<T>() ); } TE <TY T> VE<T> IFFT( CO VE<T>& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF two_power , CO T& two_power_inv , CONST_UINT_REF exponent ) { VE<T> answer{ move( FFT_Body<T>( f , N_input_start , N_input_lim , N_input_shift , two_power , exponent , InversePrimitiveRootOfTwoForFFT<T>() ) ) }; CO uint size = answer.size(); for( uint i = 0 ; i < size ; i++ ){ answer[i] *= two_power_inv; } RE answer; } TE <TY T> VE<T> IFFT( CO VE<T>& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim , CONST_UINT_REF N_output_shift , CONST_UINT_REF two_power , CO T& two_power_inv , CONST_UINT_REF exponent ) { VE<T> answer{ move( FFT_Body<T>( f , N_input_start , N_input_lim , N_input_shift , N_output_start , N_output_lim , N_output_shift , two_power , exponent , InversePrimitiveRootOfTwoForFFT<T>() ) ) }; uint size = answer.size(); CO uint N_output_length = N_output_lim - N_output_start + N_output_shift; if( size < N_output_length ){ size = N_output_length; } for( uint i = N_output_shift ; i < size ; i++ ){ answer[i] *= two_power_inv; } RE answer; } TE <TY T> static VE<T> FFT_Body( CO VE<T>& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim , CONST_UINT_REF N_output_shift , CONST_UINT_REF two_power , CONST_UINT_REF exponent , CO T ( &PRT )[LimitOfPowerForFFT<T>] ) { CO uint length = N_output_lim - N_output_start + N_output_shift; VE<T> answer( length ); if( two_power == 1 ){ if( N_input_shift == 0 && N_output_shift < length ){ if( N_input_start < N_input_lim ){ answer[N_output_shift] = f[N_input_start]; } } } else { CO T& zeta = PRT[exponent]; T zeta_power = PRT[0]; uint N_output_start_copy = N_output_start; uint digit = 0; if( N_output_start_copy != 0 ){ if( N_output_start_copy % 2 == 1 ){ zeta_power *= zeta; } N_output_start_copy /= 2; digit++; } while( N_output_start_copy != 0 ){ if( N_output_start_copy % 2 == 1 ){ zeta_power *= PRT[exponent - digit]; } N_output_start_copy /= 2; digit++; } CO uint two_power_sub = two_power / 2; CO uint exponent_sub = exponent - 1; VE<T> answer_sub0{ move( FFT_Body<T>( f , N_input_start , N_input_lim , N_input_shift , two_power_sub , exponent_sub , 0 , 2 , PRT ) ) }; VE<T> answer_sub1{ move( FFT_Body<T>( f , N_input_start , N_input_lim , N_input_shift , two_power_sub , exponent_sub , 1 , 2 , PRT ) ) }; for( uint i = N_output_start ; i < N_output_lim ; i++ ){ CO uint i_sub = i % two_power_sub; answer[i - N_output_start + N_output_shift] = answer_sub0[i_sub] + zeta_power * answer_sub1[i_sub]; zeta_power *= zeta; } } RE answer; } TE <TY T> static VE<T> FFT_Body( CO VE<T>& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF two_power , CONST_UINT_REF exponent , CONST_UINT_REF start , CONST_UINT_REF depth , CO T ( &PRT )[LimitOfPowerForFFT<T>] ) { VE<T> answer( two_power ); CO uint start_depth = start + ( ( two_power - 1 ) * depth ); CO uint N_input_length = N_input_lim - N_input_start + N_input_shift; if( start < N_input_length && N_input_shift <= start_depth ){ uint j_min; if( start < N_input_shift ){ CO uint N_input_shift_shift = N_input_shift - start; j_min = N_input_shift_shift / depth + ( N_input_shift_shift % depth == 0 ? 0 : 1 ); } else { j_min = 0; } uint j_lim; if( N_input_length <= start_depth ){ CO uint N_input_length_shift = N_input_length - start; j_lim = N_input_length_shift / depth + ( N_input_length_shift % depth == 0 ? 0 : 1 ); } else { j_lim = two_power; } CO T zero{ 0 }; uint count = 0; uint index_hit; uint j_hit; for( uint j = j_min ; j < j_lim && count < 2 ; j++ ){ CO uint index = start + j * depth - N_input_shift + N_input_start; if( f[index] != zero ){ if( count == 0 ){ index_hit = index; j_hit = j; } count++; } } if( count == 1 ){ CO T& zeta = PRT[exponent]; CO T& one = PRT[0]; T zeta_power{ one }; T zeta_power_2{ zeta }; while( j_hit != 0 ){ if( j_hit % 2 == 1 ){ zeta_power *= zeta_power_2; } zeta_power_2 *= zeta_power_2; j_hit /= 2; } answer[0] = f[index_hit]; for( uint i = 1 ; i < two_power ; i++ ){ answer[i] = zeta_power * answer[i-1]; } } else if( count > 1 ){ CO T& zeta = PRT[exponent]; CO T& one = PRT[0]; T zeta_power{ one }; constexpr CONST_UINT_REF border = BorderForFFT<T>; if( exponent < border ){ for( uint i = 0 ; i < two_power ; i++ ){ T& answer_i = answer[i]; T zeta_power_power{ one }; T zeta_power_power_2{ zeta_power }; uint j_min_copy = j_min; while( j_min_copy != 0 ){ if( j_min_copy % 2 == 1 ){ zeta_power_power *= zeta_power_power_2; } zeta_power_power_2 *= zeta_power_power_2; j_min_copy /= 2; } uint index = start + j_min * depth - N_input_shift + N_input_start; for( uint j = j_min ; j < j_lim ; j++ ){ answer_i += zeta_power_power * f[index]; zeta_power_power *= zeta_power; index += depth; } zeta_power *= zeta; } } else { CO uint two_power_sub = two_power / 2; CO uint exponent_sub = exponent - 1; CO uint depth_sub = depth * 2; VE<T> answer_sub0{ move( FFT_Body<T>( f , N_input_start , N_input_lim , N_input_shift , two_power_sub , exponent_sub , start , depth_sub , PRT ) ) }; VE<T> answer_sub1{ move( FFT_Body<T>( f , N_input_start , N_input_lim , N_input_shift , two_power_sub , exponent_sub , start + depth , depth_sub , PRT ) ) }; for( uint i = 0 ; i < two_power ; i++ ){ CO uint i_sub = i % two_power_sub; answer[i] = answer_sub0[i_sub] + zeta_power * answer_sub1[i_sub]; zeta_power *= zeta; } } } } RE answer; } TE <TY T> class TrPo; TE <TY T> class Po { friend class TrPo<T>; protected: VE<T> m_f; uint m_size; bool m_no_redundant_zero; public: IN Po(); IN Po( CO T& t ); IN Po( CO Po<T>& f ); IN Po( CONST_UINT_REF i , CO T& t ); IN Po( VE<T>&& f ); Po<T>& OP=( CO T& t ); Po<T>& OP=( CO Po<T>& f ); IN CO T& OP[]( CONST_UINT_REF i ) CO; IN T& OP[]( CONST_UINT_REF i ); IN Po<T>& OP+=( CO T& t ); Po<T>& OP+=( CO Po<T>& f ); IN Po<T>& OP-=( CO T& t ); Po<T>& OP-=( CO Po<T>& f ); Po<T>& OP*=( CO T& t ); Po<T>& OP*=( CO Po<T>& f ); Po<T>& OP/=( CO T& t ); Po<T>& OP%=( CO T& t ); IN Po<T> OP-() CO; IN CO VE<T>& GetCoefficient() CO NE; IN CO uint& size() CO NE; void RemoveRedundantZero(); IN string Display() CO NE; static IN CO Po<T>& zero(); static IN CO T& const_zero(); static IN CO T& const_one(); static IN CO T& const_minus_one(); }; TE <TY T> bool OP==( CO Po<T>& f0 , CO T& t1 ); TE <TY T> bool OP==( CO Po<T>& f0 , CO Po<T>& f1 ); TE <TY T , TY P> IN bool OP!=( CO Po<T>& f0 , CO P& f1 ); TE <TY T , TY P> IN Po<T> OP+( CO Po<T>& f0 , CO P& f1 ); TE <TY T , TY P> IN Po<T> OP-( CO Po<T>& f ); TE <TY T , TY P> IN Po<T> OP-( CO Po<T>& f0 , CO P& f1 ); TE <TY T , TY P> IN Po<T> OP*( CO Po<T>& f0 , CO P& f1 ); TE <TY T> IN Po<T> OP/( CO Po<T>& f0 , CO T& t1 ); TE <TY T> IN Po<T> OP%( CO Po<T>& f0 , CO T& t1 ); TE <TY T> IN Po<T>::Po() : m_f() , m_size( 0 ) , m_no_redundant_zero( true ) {} TE <TY T> IN Po<T>::Po( CO T& t ) : Po() { if( t != const_zero() ){ OP[]( 0 ) = t; } } TE <TY T> IN Po<T>::Po( CO Po<T>& f ) : m_f( f.m_f ) , m_size( f.m_size ) , m_no_redundant_zero( f.m_no_redundant_zero ) {} TE <TY T> IN Po<T>::Po( CONST_UINT_REF i , CO T& t ) : Po() { if( t != const_zero() ){ OP[]( i ) = t; } } TE <TY T> IN Po<T>::Po( VE<T>&& f ) : m_f( move( f ) ) , m_size( m_f.size() ) , m_no_redundant_zero( false ) {} TE <TY T> IN Po<T>& Po<T>::OP=( CO T& t ) { m_f.clear(); m_size = 0; OP[]( 0 ) = t; RE *this; } TE <TY T> IN Po<T>& Po<T>::OP=( CO Po<T>& f ) { m_f = f.m_f; m_size = f.m_size; m_no_redundant_zero = f.m_no_redundant_zero; RE *this; } TE <TY T> CO T& Po<T>::OP[]( CONST_UINT_REF i ) CO { if( m_size <= i ){ RE const_zero(); } RE m_f[i]; } TE <TY T> IN T& Po<T>::OP[]( CONST_UINT_REF i ) { m_no_redundant_zero = false; if( m_size <= i ){ CO T& z = const_zero(); while( m_size <= i ){ m_f.push_back( z ); m_size++; } } RE m_f[i]; } TE <TY T> IN Po<T>& Po<T>::OP+=( CO T& t ) { OP[]( 0 ) += t; RE *this; } TE <TY T> Po<T>& Po<T>::OP+=( CO Po<T>& f ) { for( uint i = 0 ; i < f.m_size ; i++ ){ OP[]( i ) += f.m_f[i]; } RE *this; } TE <TY T> IN Po<T>& Po<T>::OP-=( CO T& t ) { OP[]( 0 ) -= t; RE *this; } TE <TY T> Po<T>& Po<T>::OP-=( CO Po<T>& f ) { for( uint i = 0 ; i < f.m_size ; i++ ){ OP[]( i ) -= f.m_f[i]; } RE *this; } TE <TY T> Po<T>& Po<T>::OP*=( CO T& t ) { if( m_size == 0 || t == const_one() ){ RE *this; } if( t == const_zero() ){ RE OP=( zero() ); } for( uint i = 0 ; i < m_size ; i++ ){ OP[]( i ) *= t; } RE *this; } TE <TY T> Po<T>& Po<T>::OP*=( CO Po<T>& f ) { if( m_size == 0 ){ RE *this; } if( f.m_size == 0 ){ RE OP=( zero() ); } CO uint size = m_size + f.m_size - 1; Po<T> product{}; for( uint i = 0 ; i < size ; i++ ){ T& product_i = product[i]; CO uint j_min = m_size <= i ? i - m_size + 1 : 0; CO 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]; } } RE OP=( product ); } TE <TY T> Po<T>& Po<T>::OP/=( CO T& t ) { if( t == const_one() ){ RE *this; } RE *this; } TE <TY T> Po<T>& Po<T>::OP%=( CO T& t ) { if( t == const_one() ){ RE OP=( zero() ); } for( uint i = 0 ; i < m_size ; i++ ){ OP[]( i ) %= t; } RE *this; } TE <TY T> IN Po<T> Po<T>::OP-() CO { Po<T>().OP-=( *this ); } TE <TY T> IN CO VE<T>& Po<T>::GetCoefficient() CO NE { RE m_f; } TE <TY T> IN CO uint& Po<T>::size() CO NE { RE m_size; } TE <TY T> void Po<T>::RemoveRedundantZero() { if( m_no_redundant_zero ){ RE; } CO T& z = const_zero(); while( m_size > 0 ? m_f[m_size - 1] == z : false ){ m_f.pop_back(); m_size--; } m_no_redundant_zero = true; RE; } TE <TY T> string Po<T>::Display() CO NE { 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 += ")"; RE s; } TE <TY T> IN CO Po<T>& Po<T>::zero() { static CO Po<T> z{}; RE z; } TE <TY T> IN CO T& Po<T>::const_zero() { static CO T z{ 0 }; RE z; } TE <TY T> IN CO T& Po<T>::const_one() { static CO T o{ 1 }; RE o; } TE <TY T> IN CO T& Po<T>::const_minus_one() { static CO T m{ -1 }; RE m; } TE <TY T> bool OP==( CO Po<T>& f0 , CO T& t1 ) { CO uint& size = f0.size(); CO T& zero = Po<T>::const_zero(); for( uint i = 1 ; i < size ; i++ ){ if( f0[i] != zero ){ RE false; } } RE f0[0] == t1; } TE <TY T> bool OP==( CO Po<T>& f0 , CO Po<T>& f1 ) { CO uint& size0 = f0.size(); CO uint& size1 = f1.size(); CO uint& size = size0 < size1 ? size1 : size0; for( uint i = 0 ; i < size ; i++ ){ if( f0[i] != f1[i] ){ RE false; } } RE true; } TE <TY T , TY P> IN bool OP!=( CO Po<T>& f0 , CO P& f1 ) { RE !( f0 == f1 ); } TE <TY T , TY P> IN Po<T> OP+( CO Po<T>& f0 , CO P& f1 ) { Po<T> f = f0; f += f1; RE f; } TE <TY T , TY P> IN Po<T> OP-( CO Po<T>& f ) { RE Po<T>::zero() - f; } TE <TY T , TY P> IN Po<T> OP-( CO Po<T>& f0 , CO P& f1 ) { Po<T> f = f0; RE f.OP-=( f1 ); } TE <TY T , TY P> IN Po<T> OP*( CO Po<T>& f0 , CO P& f1 ) { Po<T> f = f0; RE f.OP*=( f1 ); } TE <TY T> IN Po<T> OP/( CO Po<T>& f0 , CO T& t1 ) { Po<T> f = f0; RE f.OP/=( t1 ); } TE <TY T> IN Po<T> OP%( CO Po<T>& f0 , CO T& t1 ) { Po<T> f = f0; RE f.OP%=( t1 ); } TE <TY T> class TrPo; TE <TY T> TrPo<T> TrDifferential( CO TrPo<T>& f , CONST_UINT_REF N_output_start_plus_one ); TE <TY T> TrPo<T> TrIntegral( CO TrPo<T>& f , CONST_UINT_REF N_output_start ); TE <TY T> class TrPo : public Po<T> { friend TrPo<T> TrDifferential<T>( CO TrPo<T>& f , CONST_UINT_REF N_output_start_plus_one ); friend TrPo<T> TrIntegral<T>( CO TrPo<T>& f , CONST_UINT_REF N_output_start ); private: uint m_N; public: IN TrPo( CONST_UINT_REF N = 0 ); IN TrPo( CO TrPo<T>& f ); IN TrPo( CONST_UINT_REF N , CO T& t ); TrPo( CONST_UINT_REF N , CO Po<T>& f ); IN TrPo( CONST_UINT_REF N , CONST_UINT_REF i , CO T& t ); IN TrPo( CONST_UINT_REF N , VE<T>&& f ); IN TrPo<T>& OP=( CO TrPo<T>& f ); IN TrPo<T>& OP=( CO T& t ); IN TrPo<T>& OP=( CO Po<T>& f ); IN TrPo<T>& OP+=( CO T& t ); IN TrPo<T>& OP+=( CO Po<T>& f ); TrPo<T>& TrPlus( CO Po<T>& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_limit ); IN TrPo<T>& OP-=( CO T& t ); IN TrPo<T>& OP-=( CO Po<T>& f ); TrPo<T>& TrMinus( CO Po<T>& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_limit ); IN TrPo<T>& OP*=( CO T& t ); TrPo<T>& OP*=( CO Po<T>& f ); TrPo<T>& FFT_Multiplication( CO Po<T>& f ); TrPo<T>& TrMultiplication( CO Po<T>& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ); TrPo<T>& FFT_TrMultiplication( CO Po<T>& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ); TrPo<T> TrMultiplication_const( CO Po<T>& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ) CO; TrPo<T> FFT_TrMultiplication_const( CO Po<T>& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ) CO; IN TrPo<T>& OP/=( CO T& t ); IN TrPo<T>& OP/=( CO TrPo<T>& t ); IN TrPo<T>& OP%=( CO T& t ); IN TrPo<T> OP-() CO; IN void SetTruncation( CONST_UINT_REF N ) NE; IN CO uint& GetTruncation() CO NE; IN TrPo<T>& TruncateInitial( CONST_UINT_REF N ) NE; IN TrPo<T>& TruncateFinal( CONST_UINT_REF N ) NE; }; TE <TY T> IN constexpr CO uint FFT_Multiplication_border_0; TE <TY T> IN constexpr CO uint FFT_Multiplication_border_1; TE <TY T> IN constexpr CO uint FFT_Multiplication_border_1_2; TE <TY T> IN constexpr CO uint FFT_Multiplication_border_1_2_exponent; TE <TY T> IN constexpr CO uint FFT_Multiplication_border_1_2_inv; TE <TY T , TY P> IN TrPo<T> OP+( CO TrPo<T>& f0 , CO P& f1 ); TE <TY T , TY P> IN TrPo<T> OP-( CO TrPo<T>& f ); TE <TY T , TY P> IN TrPo<T> OP-( CO TrPo<T>& f0 , CO P& f1 ); TE <TY T , TY P> IN TrPo<T> OP*( CO TrPo<T>& f0 , CO P& f1 ); TE <TY T , TY P> IN TrPo<T> OP/( CO TrPo<T>& f0 , CO P& f1 ); TE <TY T> IN TrPo<T> OP%( CO TrPo<T>& f0 , CO T& t1 ); TE <TY T> IN TrPo<T> Differential( CO TrPo<T>& f ); TE <TY T> IN TrPo<T> Differential( CONST_UINT_REF i , CO TrPo<T>& f ); TE <TY T> TrPo<T> TrDifferential( CO TrPo<T>& f , CONST_UINT_REF N_output_start_plus_one ); TE <TY T> IN TrPo<T> Integral( CO TrPo<T>& f ); TE <TY T> TrPo<T> TrIntegral( CO TrPo<T>& f , CONST_UINT_REF N_output_start ); TE <TY T> TrPo<T> Inverse( CO TrPo<T>& f ); TE <TY T> TrPo<T> Exp( CO TrPo<T>& f ); TE <TY T> IN TrPo<T> Log( CO TrPo<T>& f ); TE <TY T> TrPo<T> Power( CO TrPo<T>& f , CO T& t ); TE <TY T> IN TrPo<T>::TrPo( CONST_UINT_REF N ) : Po<T>() , m_N( N ) {} TE <TY T> IN TrPo<T>::TrPo( CO TrPo<T>& f ) : Po<T>( f ) , m_N( f.m_N ) {} TE <TY T> IN TrPo<T>::TrPo( CONST_UINT_REF N , CO T& t ) : Po<T>( t ) , m_N( N ) {} TE <TY T> TrPo<T>::TrPo( CONST_UINT_REF N , CO Po<T>& f ) : Po<T>() , m_N( N ) { CO uint& size = f.Po<T>::m_size < m_N ? f.Po<T>::m_size : m_N; for( uint i = 0 ; i < size ; i++ ){ Po<T>::m_f.push_back( f.Po<T>::m_f[i] ); Po<T>::m_size++; } } TE <TY T> IN TrPo<T>::TrPo( CONST_UINT_REF N , CONST_UINT_REF i , CO T& t ) : Po<T>() , m_N( N ) { if( i < m_N ? t != Po<T>::const_zero() : false ){ Po<T>::OP[]( i ) = t; } } TE <TY T> IN TrPo<T>::TrPo( CONST_UINT_REF N , VE<T>&& f ) : Po<T>( move( f ) ) , m_N( N ) { while( Po<T>::m_size > m_N ){ Po<T>::m_f.pop_back(); Po<T>::m_size--; } } TE <TY T> IN TrPo<T>& TrPo<T>::OP=( CO TrPo<T>& f ) { Po<T>::OP=( f ); m_N = f.m_N; RE *this; } TE <TY T> IN TrPo<T>& TrPo<T>::OP=( CO T& t ) { Po<T>::OP=( t ); RE *this; } TE <TY T> IN TrPo<T>& TrPo<T>::OP=( CO Po<T>& f ) { RE OP=( TrPo<T>( m_N , f ) ); } TE <TY T> IN TrPo<T>& TrPo<T>::OP+=( CO T& t ) { Po<T>::OP+=( t ); RE *this; } TE <TY T> IN TrPo<T>& TrPo<T>::OP+=( CO Po<T>& f ) { RE TrPo<T>::TrPlus( f , 0 , f.Po<T>::m_size ); } TE <TY T> TrPo<T>& TrPo<T>::TrPlus( CO Po<T>& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_limit ) { CO uint& size = N_output_limit < m_N ? N_output_limit < f.Po<T>::m_size ? N_output_limit : f.Po<T>::m_size : m_N < f.Po<T>::m_size ? m_N : f.Po<T>::m_size; CO uint& size_min = Po<T>::m_size < size ? Po<T>::m_size : size; for( uint i = N_output_start ; i < size_min ; i++ ){ Po<T>::m_f[i] += f.Po<T>::m_f[i]; } for( uint i = Po<T>::m_size ; i < size ; i++ ){ Po<T>::m_f.push_back( f.Po<T>::m_f[i] ); Po<T>::m_size++; } RE *this; } TE <TY T> IN TrPo<T>& TrPo<T>::OP-=( CO T& t ) { Po<T>::OP-=( t ); RE *this; } TE <TY T> IN TrPo<T>& TrPo<T>::OP-=( CO Po<T>& f ) { RE TrPo<T>::TrMinus( f , 0 , f.Po<T>::m_size ); } TE <TY T> TrPo<T>& TrPo<T>::TrMinus( CO Po<T>& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_limit ) { CO uint& size = N_output_limit < m_N ? N_output_limit < f.Po<T>::m_size ? N_output_limit : f.Po<T>::m_size : m_N < f.Po<T>::m_size ? m_N : f.Po<T>::m_size; CO uint& size_min = Po<T>::m_size < size ? Po<T>::m_size : size; for( uint i = N_output_start ; i < size_min ; i++ ){ Po<T>::m_f[i] -= f.Po<T>::m_f[i]; } for( uint i = Po<T>::m_size ; i < size ; i++ ){ Po<T>::m_f.push_back( - f.Po<T>::m_f[i] ); Po<T>::m_size++; } RE *this; } TE <TY T> IN TrPo<T>& TrPo<T>::OP*=( CO T& t ) { Po<T>::OP*=( t ); RE *this; } TE <TY T> TrPo<T>& TrPo<T>::OP*=( CO Po<T>& f ) { constexpr CO uint border_0 = 21; CO T& zero = Po<T>::const_zero(); bool searching = true; if( Po<T>::m_size < border_0 && f.Po<T>::m_size < border_0 ){ RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( f.Po<T>::m_size == 0 ); DEFINITION_0_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } else { DEFINITION_1_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( searching ); DEFINITION_2_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; CO uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N; RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= m_N ); DEFINITION_3_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } RE *this; } TE <TY T> TrPo<T>& TrPo<T>::FFT_Multiplication( CO Po<T>& f ) { constexpr CONST_UINT_REF border_0 = FFT_Multiplication_border_0<T>; CO T& zero = Po<T>::const_zero(); bool searching = true; if( Po<T>::m_size < border_0 && f.Po<T>::m_size < border_0 ){ RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( f.Po<T>::m_size == 0 ); DEFINITION_0_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } else { DEFINITION_1_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( searching ); DEFINITION_2_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; CO uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N; RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed ); CO uint N_input_truncated_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1; constexpr CONST_UINT_REF border_1 = FFT_Multiplication_border_1<T>; if( N_input_truncated_deg_0_deg_1 < border_1 ){ DEFINITION_3_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } else { DEFINITION_4_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; Po<T>::m_f = move( IFFT<T>( f0 , 0 , two_power , 0 , N_input_start_0_start_1 , N_output_lim_fixed , N_input_start_0_start_1 , two_power , two_power_inv , exponent ) ); Po<T>::m_size = Po<T>::m_f.size(); } } RE *this; } TE <TY T> TrPo<T>& TrPo<T>::TrMultiplication( CO Po<T>& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ) { constexpr CO uint border_0 = 21; CO T& zero = Po<T>::const_zero(); bool searching = true; if( Po<T>::m_size < border_0 && f.Po<T>::m_size < border_0 ){ DEFINITION_0_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } else { DEFINITION_1_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; DEFINITION_2_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N; if( N_output_lim_fixed > N_output_lim ){ N_output_lim_fixed = N_output_lim; } RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed ); DEFINITION_3_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } RE *this; } TE <TY T> TrPo<T>& TrPo<T>::FFT_TrMultiplication( CO Po<T>& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ) { constexpr CONST_UINT_REF border_0 = FFT_Multiplication_border_0<T>; CO T& zero = Po<T>::const_zero(); bool searching = true; if( Po<T>::m_size < border_0 && f.Po<T>::m_size < border_0 ){ DEFINITION_0_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } else { DEFINITION_1_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; DEFINITION_2_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N; if( N_output_lim_fixed > N_output_lim ){ N_output_lim_fixed = N_output_lim; } RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed ); CO uint N_input_truncated_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1; constexpr CONST_UINT_REF border_1 = FFT_Multiplication_border_1<T>; if( N_input_truncated_deg_0_deg_1 < border_1 ){ DEFINITION_3_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } else { DEFINITION_4_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; uint N_output_start_shifted; uint N_output_shift_shifted; if( N_output_start < N_input_start_0_start_1 ){ N_output_start_shifted = 0; N_output_shift_shifted = N_input_start_0_start_1; } else { N_output_start_shifted = N_output_start - N_input_start_0_start_1; N_output_shift_shifted = N_output_start; } CO uint N_output_lim_shifted = N_output_lim_fixed - N_input_start_0_start_1; f0 = move( IFFT<T>( f0 , 0 , two_power , 0 , N_output_start_shifted , N_output_lim_shifted , N_output_shift_shifted , two_power , two_power_inv , exponent ) ); SET_VECTOR_FOR_ANSWER_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( N_output_lim_fixed ); for( uint i = N_output_start ; i < N_output_lim_fixed ; i++ ){ Po<T>::m_f[i] = f0[i]; } } } RE *this; } TE <TY T> TrPo<T> TrPo<T>::TrMultiplication_const( CO Po<T>& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ) CO { constexpr CO uint border_0 = 21; CO T& zero = Po<T>::const_zero(); bool searching = true; if( Po<T>::m_size < border_0 && f.Po<T>::m_size < border_0 ){ DEFINITION_0_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL; RE TrPo<T>( m_N , move( answer ) ); } DEFINITION_1_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL; DEFINITION_2_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL; uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N; if( N_output_lim_fixed > N_output_lim ){ N_output_lim_fixed = N_output_lim; } RETURN_ZERO_FOR_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed ); DEFINITION_3_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL; RE TrPo<T>( m_N , move( answer ) ); } TE <TY T> TrPo<T> TrPo<T>::FFT_TrMultiplication_const( CO Po<T>& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ) CO { constexpr CONST_UINT_REF border_0 = FFT_Multiplication_border_0<T>; CO T& zero = Po<T>::const_zero(); bool searching = true; if( Po<T>::m_size < border_0 && f.Po<T>::m_size < border_0 ){ DEFINITION_0_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL; RE TrPo<T>( m_N , move( answer ) ); } DEFINITION_1_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL; DEFINITION_2_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL; uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N; if( N_output_lim_fixed > N_output_lim ){ N_output_lim_fixed = N_output_lim; } RETURN_ZERO_FOR_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed ); CO uint N_input_truncated_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1; constexpr CONST_UINT_REF border_1 = FFT_Multiplication_border_1<T>; if( N_input_truncated_deg_0_deg_1 < border_1 ){ DEFINITION_3_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL; RE TrPo<T>( m_N , move( answer ) ); } DEFINITION_4_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL; uint N_output_start_shifted; uint N_output_shift_shifted; if( N_output_start < N_input_start_0_start_1 ){ N_output_start_shifted = 0; N_output_shift_shifted = N_input_start_0_start_1; } else { N_output_start_shifted = N_output_start - N_input_start_0_start_1; N_output_shift_shifted = N_output_start; } CO uint N_output_lim_shifted = N_output_lim_fixed - N_input_start_0_start_1; RE TrPo<T>( m_N , move( IFFT<T>( f0 , 0 , two_power , 0 , N_output_start_shifted , N_output_lim_shifted , N_output_shift_shifted , two_power , two_power_inv , exponent ) ) ); } TE <TY T> IN TrPo<T>& TrPo<T>::OP/=( CO T& t ) { Po<T>::OP/=( t ); RE *this; } TE <TY T> IN TrPo<T>& TrPo<T>::OP/=( CO TrPo<T>& f ) { RE OP*=( Inverse( m_N == f.m_N ? f : TrPo<T>( m_N , f ) ) ); } TE <TY T> IN TrPo<T>& TrPo<T>::OP%=( CO T& t ) { Po<T>::OP%=( t ); RE *this; } TE <TY T> IN TrPo<T> TrPo<T>::OP-() CO { RE TrPo<T>( m_N ).OP-=( *this ); } TE <TY T> IN void TrPo<T>::SetTruncation( CONST_UINT_REF N ) NE { m_N = N; TruncateFinal( m_N ); } TE <TY T> IN CO uint& TrPo<T>::GetTruncation() CO NE { RE m_N; } TE <TY T> IN TrPo<T>& TrPo<T>::TruncateInitial( CONST_UINT_REF N ) NE { CONST_UINT_REF size = N < Po<T>::m_size ? N : Po<T>::m_size; for( uint i = 0 ; i < size ; i++ ){ Po<T>::m_f[i] = 0; } RE *this; } TE <TY T> IN TrPo<T>& TrPo<T>::TruncateFinal( CONST_UINT_REF N ) NE { while( Po<T>::m_size > N ){ Po<T>::m_f.pop_back(); Po<T>::m_size--; } RE *this; } TE <TY T , TY P> IN TrPo<T> OP+( CO TrPo<T>& f0 , CO P& f1 ) { RE TrPo<T>( f0 ).OP+=( f1 ); } TE <TY T , TY P> IN TrPo<T> OP-( CO TrPo<T>& f ) { RE TrPo<T>( f ).OP*=( Po<T>::const_minus_one()); } TE <TY T , TY P> IN TrPo<T> OP-( CO TrPo<T>& f0 , CO P& f1 ) { RE TrPo<T>( f0 ).OP-=( f1 ); } TE <TY T , TY P> IN TrPo<T> OP*( CO TrPo<T>& f0 , CO P& f1 ) { RE TrPo<T>( f0 ).OP*=( f1 ); } TE <TY T , TY P> IN TrPo<T> OP/( CO TrPo<T>& f0 , CO P& f1 ) { RE TrPo<T>( f0 ).OP*=( Inverse( f1 ) ); } TE <TY T> IN TrPo<T> OP%( CO TrPo<T>& f0 , CO T& t1 ) { RE TrPo<T>( f0 ).OP%=( t1 ); } TE <TY T> IN TrPo<T> Differential( CO TrPo<T>& f ) { RE TrDifferential<T>( f , 1 ); } TE <TY T> IN TrPo<T> Differential( CONST_UINT_REF i , CO TrPo<T>& f ) { RE i == 0 ? f : Differential<T>( i - 1 , Differential<T>( f ) ); } TE <TY T> TrPo<T> TrDifferential( CO TrPo<T>& f , CONST_UINT_REF N_output_start_plus_one ) { if( f.m_N == 0 ){ RE TrPo<T>(); } TrPo<T> f_dif{ f.m_N - 1 }; if( N_output_start_plus_one < f.Po<T>::m_size ){ for( uint i = 1 ; i < N_output_start_plus_one ; i++ ){ f_dif.Po<T>::m_f.push_back( 0 ); } for( uint i = N_output_start_plus_one ; i < f.Po<T>::m_size ; i++ ){ f_dif.Po<T>::m_f.push_back( i * f.Po<T>::m_f[i] ); } f_dif.Po<T>::m_size = f.Po<T>::m_size - 1; } RE f_dif; } TE <TY T> IN TrPo<T> Integral( CO TrPo<T>& f ) { RE TrIntegral<T>( f , 1 ); } TE <TY T> TrPo<T> TrIntegral( CO TrPo<T>& f , CONST_UINT_REF N_output_start ) { TrPo<T> f_int{ f.m_N + 1 }; if( N_output_start <= f.Po<T>::m_size ){ for( uint i = 0 ; i < N_output_start ; i++ ){ f_int.Po<T>::m_f.push_back( 0 ); } for( uint i = N_output_start ; i <= f.Po<T>::m_size ; i++ ){ f_int.Po<T>::m_f.push_back( f.Po<T>::m_f[i - 1] / T( i ) ); } f_int.Po<T>::m_size = f.Po<T>::m_size + 1; } RE f_int; } TE <TY T> TrPo<T> Inverse( CO TrPo<T>& f ) { DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( T , f_inv.TrMinus( f_inv.TrMultiplication_const( f , power , power_2 ).TrMultiplication( f_inv , power , power_2 ) , power , power_2 ) ); } TE <TY T> TrPo<T> Exp( CO TrPo<T>& f ) { DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( T , f_exp.TrMinus( ( TrIntegral( Differential( f_exp ).TrMultiplication_const( Inverse( f_exp ) , power - 1 , power_2 ) , power ).TrMinus( f , power , power_2 ) ).TrMultiplication( f_exp , power ) , power , power_2 ) ); } TE <TY T> IN TrPo<T> Log( CO TrPo<T>& f ) { RE Integral<T>( Differential<T>( f ) /= f ); } TE <TY T> IN TrPo<T> Power( CO TrPo<T>& f , CO T& t ) { RE Exp( Log( f ) *= t ); } DEFINITION_OF_PARTIAL_SPECIALISATION_OF_MULTIPLICATION_OF_TRUNCATED_POLYNOMIAL( MOD , 4 , 4 , 8 , 3 , 873463809 ); int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); ll N; cin >> N; ll A[100000]; ll sum = 0; FOR( i , 0 , N ){ ll& Ai = A[i]; cin >> Ai; sum += Ai; } MOD coef{}; MOD one = MOD( 1 ); ll D_signed = sum - Q + 1; if( D_signed > 0 ){ sort( A , A + N ); uint B[100000]; ll count[100000]; ll Ai_prev = 0; ll num = -1; FOR( i , 0 , N ){ ll& Ai = A[i]; if( Ai_prev == Ai ){ count[num]++; } else if( Ai < D_signed ){ num++; B[num] = uint( Ai ); count[num] = 1; Ai_prev = Ai; } else { i = N; } } uint D = uint( D_signed ); TrPo<MOD> f{ D }; num++; FOR( i , 0 , num ){ uint& Bi = B[i]; MOD count_i{ count[i] }; uint j_lim = ( D - 1 ) / Bi + 1; uint d = 0; FOR( j , 1 , j_lim ){ d += Bi; if( j % 2 == 0 ){ f[d] -= count_i / j; } else { f[d] += count_i / j; } } } f = move( Exp<MOD>( f ) ); FOR( i , 0 , D ){ coef += f[i]; } } MOD m{ one }; MOD power{ 2 }; N--; while( N != 0 ){ if( N % 2 == 1 ){ m *= power; } power = power * power; N /= 2; } cout << ( m * sum - coef * Q ).Represent() << "\n"; RE 0; }

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード