#827933 (C++17) No.2166 Paint and Fill

提出ソース
結果

問題	No.2166 Paint and Fill
ユーザー	👑 p-adic
提出日時	2022-12-23 14:08:09
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	62,300 bytes
コンパイル時間	7,765 ms
コンパイル使用メモリ	314,612 KB
実行使用メモリ	204,924 KB
最終ジャッジ日時	2024-04-29 04:15:10
合計ジャッジ時間	25,226 ms
ジャッジサーバーID （参考情報）	judge2 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 6,016 KB
testcase_01	AC	1,977 ms 45,596 KB
testcase_02	AC	2,687 ms 204,924 KB
testcase_03	AC	87 ms 9,728 KB
testcase_04	AC	89 ms 9,728 KB
testcase_05	AC	86 ms 9,728 KB
testcase_06	AC	89 ms 9,856 KB
testcase_07	AC	91 ms 9,600 KB
testcase_08	TLE	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include <bits/stdc++.h>
using namespace std;using uint = unsigned int;using ll = long long;
#define PU public
#define PR PU
#define TE template
#define TY typename
#define ST static
#define IN inline
#define OP operator
#define CE constexpr
#define CO const
#define RE return 
#define NE noexcept
#define VE vector
#define LI list
#define TYPE_OF(VAR) remove_const<remove_reference<decltype(VAR)>::type >::type
#define UNTIE ios_base::sync_with_stdio(false); cin.tie(nullptr) 
#define CEXPR(LL,BOUND,VALUE) CE CO LL BOUND = VALUE 
#define CIN(LL,A) LL A; cin >> A 
#define ASSERT(A,MIN,MAX) assert(MIN <= A && A <= MAX) 
#define CIN_ASSERT(A,MIN,MAX) CIN(TYPE_OF(MAX),A); 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 FOREQINV(VAR,INITIAL,FINAL) for(TYPE_OF(INITIAL) VAR = INITIAL;VAR >= FINAL;VAR --) 
#define FOR_I(ARRAY,I,END) for(auto I = ARRAY .begin(),END = ARRAY .end();I != END;I ++) 
#define REPEAT(HOW_MANY_TIMES) FOR(VARIABLE_FOR_REPEAT,0,HOW_MANY_TIMES) 
#define QUIT RE 0 
#define COUT(AN) cout << (AN) << "\n"; 
#define RETURN(AN) COUT(AN); QUIT 
TE <TY T> IN T Residue(CO T& a,CO T& p){ RE a >= 0 ? a % p:p - (- a - 1) % p - 1; }
#define RE_ZR_FOR_MU_FOR_TR_PO_IF( CD) if( CD){ RE OP=(zero); } 
#define RE_ZR_FOR_TR_MU_CO_FOR_TR_PO_IF( CD) if( CD){ RE TRPO<T>(m_N); } 
#define SET_VE_FOR_AN_OF_MU_FOR_TR_PO(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_VE_FOR_AN_OF_TR_MU_CO_FOR_TR_PO(N_OUTPUT_LIM) VE<T> answer(N_OUTPUT_LIM) 
#define SET_SUM_OF_MU_FOR_TR_PO PO<T>::m_f[i] = sum 
#define SET_SUM_OF_TR_MU_CO_FOR_TR_PO answer[i] = sum 
#define SET_N_INPUT_START_FOR_MU_FOR_TR_PO(F,SIZE,N_INPUT_START_NUM) uint N_INPUT_START_NUM; for(uint i = 0;i < SIZE && SE;i++){ if(F[i] != zero){ N_INPUT_START_NUM = i; SE = false; } } 
#define SET_N_INPUT_MAX_FOR_MU_FOR_TR_PO(F,SIZE,N_INPUT_MAX_NUM) uint N_INPUT_MAX_NUM; SE = true; for(uint i = (SIZE) - 1;SE;i--){ if(F[i] != zero){ N_INPUT_MAX_NUM = i; SE = false; } } 
#define CONVOLUTION_FOR_MU_FOR_TR_PO(J_MIN) CO uint j_max = i < N_IPT_max_0_start_1 ? i - N_IPT_start_1:N_IPT_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_TR_MU_CO_FOR_TR_PO(J_MIN) CO uint j_max = i < N_IPT_max_0_start_1 ? i - N_IPT_start_1:N_IPT_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 ZN_FOR_MU_FOR_TR_PO for(uint i = 0;i < N_IPT_start_0_start_1;i++){ PO<T>::m_f[i] = 0; } 
#define ZN_FOR_TR_MU_CO_FOR_TR_PO for(uint i = 0;i < N_IPT_start_0_start_1;i++){ answer[i] = 0; } 
#define CN(S1,S2) SUBSTITUTE_CN(S1,S2) 
#define SUBSTITUTE_CN(S1,S2) S1 ## S2 
#define DF_0_OF__FOR_TR_PO(MU,ACCESS_ENTRY) CN(CN(RE_ZR_FOR_,MU),_FOR_TR_PO_IF)(PO<T>::m_size == 0); uint N_OPT_max = PO<T>::m_size + f.PO<T>::m_size - 2; if(N_OPT_max >= m_N){ N_OPT_max = m_N - 1; } CO uint N_OPT_lim = N_OPT_max + 1; CN(CN(SET_VE_FOR_AN_OF_,MU),_FOR_TR_PO)(N_OPT_lim); for(uint i = N_OPT_max;SE;i--){ T sum{ zero }; for(uint j = 0;j <= i;j++){ sum += ACCESS_ENTRY * f.PO<T>::OP[](i - j); } CN(CN(SET_SUM_OF_,MU),_FOR_TR_PO); SE = i > 0; } 
#define DF_0_OF_MU_FOR_TR_PO DF_0_OF__FOR_TR_PO(MU,PO<T>::m_f[j]) 
#define DF_0_OF_TR_MU_CO_FOR_TR_PO DF_0_OF__FOR_TR_PO(TR_MU_CO,PO<T>::OP[](j)) 
#define DF_1_OF__FOR_TR_PO(MU) SET_N_INPUT_START_FOR_MU_FOR_TR_PO(PO<T>::m_f,PO<T>::m_size,N_IPT_start_0); CN(CN(RE_ZR_FOR_,MU),_FOR_TR_PO_IF)(SE); SE = true; SET_N_INPUT_START_FOR_MU_FOR_TR_PO(f,f.PO<T>::m_size,N_IPT_start_1); 
#define DF_1_OF_MU_FOR_TR_PO DF_1_OF__FOR_TR_PO(MU) 
#define DF_1_OF_TR_MU_CO_FOR_TR_PO DF_1_OF__FOR_TR_PO(TR_MU_CO) 
#define DF_2_OF_MU_FOR_TR_PO SET_N_INPUT_MAX_FOR_MU_FOR_TR_PO(PO<T>::m_f,PO<T>::m_size,N_IPT_max_0); SET_N_INPUT_MAX_FOR_MU_FOR_TR_PO(f,f.PO<T>::m_size < m_N ? f.PO<T>::m_size:m_N,N_IPT_max_1); CO uint N_IPT_max_0_max_1 = N_IPT_max_0 + N_IPT_max_1; CO uint N_IPT_start_0_start_1 = N_IPT_start_0 + N_IPT_start_1; 
#define DF_2_OF_TR_MU_CO_FOR_TR_PO DF_2_OF_MU_FOR_TR_PO 
#define DF_3_OF__FOR_TR_PO(MU) CO uint N_IPT_start_0_max_1 = N_IPT_start_0 + N_IPT_max_1; CO uint N_IPT_max_0_start_1 = N_IPT_max_0 + N_IPT_start_1; CO uint N_OPT_max_fixed = N_OPT_lim_fixed - 1; CN(CN(SET_VE_FOR_AN_OF_,MU),_FOR_TR_PO)(N_OPT_lim_fixed); for(uint i = N_OPT_max_fixed;i > N_IPT_start_0_max_1;i--){ CN(CN(CONVOLUTION_FOR_,MU),_FOR_TR_PO)(i - N_IPT_max_1); } SE = true; for(uint i = N_IPT_start_0_max_1 < N_OPT_max_fixed ? N_IPT_start_0_max_1:N_OPT_max_fixed;SE;i--){ CN(CN(CONVOLUTION_FOR_,MU),_FOR_TR_PO)(N_IPT_start_0); SE = i > N_IPT_start_0_start_1; } CN(CN(ZN_FOR_,MU),_FOR_TR_PO); 
#define DF_3_OF_MU_FOR_TR_PO DF_3_OF__FOR_TR_PO(MU) 
#define DF_3_OF_TR_MU_CO_FOR_TR_PO DF_3_OF__FOR_TR_PO(TR_MU_CO) 
#define DF_4_OF_MU_FOR_TR_PO uint two_power = FFT_MU_border_1_2<T>; uint exponent = FFT_MU_border_1_2_exponent<T>; T two_power_inv{ FFT_MU_border_1_2_inv<T> }; while(N_IPT_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_IPT_start_0,N_IPT_max_0 + 1,0,two_power,exponent)) }; CO VE<T> f1{ move(FFT<T>(f.PO<T>::m_f,N_IPT_start_1,N_IPT_max_1 + 1,0,two_power,exponent)) }; for(uint i = 0;i < two_power;i++){ f0[i] *= f1[i]; } 
#define DF_4_OF_TR_MU_CO_FOR_TR_PO DF_4_OF_MU_FOR_TR_PO 
#define DF_OF_INVERSE_FOR_TR_PO(TYPE,RECURSION) CO uint& N = f.GetTruncation(); uint power; uint power_2 = 1; TRPO< TYPE > f_inv{ power_2,PO< TYPE >::CO_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 DF_OF_EXP_FOR_TR_PO(TYPE,RECURSION) CO uint& N = f.GetTruncation(); uint power; uint power_2 = 1; TRPO< TYPE > f_exp{ power_2,PO< TYPE >::CO_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 DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_TR_PO(TYPE,BORDER_0,BORDER_1,BORDER_1_2,BORDER_1_2_EXPONENT,BORDER_1_2_INV) TE <> CE CO uint FFT_MU_border_0< TYPE > = BORDER_0; TE <> CE CO uint FFT_MU_border_1< TYPE > = BORDER_1; TE <> CE CO uint FFT_MU_border_1_2< TYPE > = BORDER_1_2; TE <> CE CO uint FFT_MU_border_1_2_exponent< TYPE > = BORDER_1_2_EXPONENT; TE <> CE CO uint FFT_MU_border_1_2_inv< TYPE > = BORDER_1_2_INV; TE <> IN TRPO< TYPE >& TRPO< TYPE >::OP*=(CO PO< TYPE >& f) { RE TRPO< TYPE >::FFT_MU(f); } TE <> TRPO< TYPE > Inverse(CO TRPO< TYPE >& f) { DF_OF_INVERSE_FOR_TR_PO(TYPE,f_inv.TRMinus(f_inv.FFT_TRMU_CO(f,power,power_2).FFT_TRMU(f_inv,power,power_2),power,power_2)); } TE <> TRPO< TYPE > Exp(CO TRPO< TYPE >& f) { DF_OF_EXP_FOR_TR_PO(TYPE,f_exp.TRMinus((TRIntegral(Differential(f_exp).FFT_TRMU_CO(Inverse(f_exp),power - 1,power_2),power).TRMinus(f,power,power_2)).FFT_TRMU(f_exp,power,power_2),power,power_2)); } 
#define DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(TYPE) TE <> PO<TYPE>& PO<TYPE>::OP*=(CO PO<TYPE>& f) { if(m_size != 0){ VE<TYPE> v{}; v.swap(m_f); TRPO<TYPE> f_copy{ m_size + f.m_size - 1,move(v) }; f_copy *= f; m_f = move(f_copy.PO<TYPE>::m_f); m_size = m_f.size(); } RE *this; } 
#define SET_MATRIX_MULTIPOINT_EVALUATION(SAMPLE_NUM_MAX,POINT) point = move(VE<T>(SAMPLE_NUM_MAX + 1)); for(uint t = 0;t <= SAMPLE_NUM_MAX;t++){ point[t] = POINT; } VE<T> eval[Y][Y] = {}; for(uint y = 0;y < Y;y++){ CO VE<PO<T> >& M_ref_y = M_ref[y]; VE<T> (&eval_y)[Y] = eval[y]; for(uint x = 0;x < Y;x++){ SetMultipointEvaluation(M_ref_y[x],point,eval_y[x]); } } VE<MA<Y,Y,T> > sample(SAMPLE_NUM_MAX + 1,MA<Y,Y,T>::Zero()); for(uint t = 0;t <= SAMPLE_NUM_MAX;t++){ VE<VE<T> >& sample_t_ref = sample[t].RefTable(); for(uint y = 0;y < Y;y++){ VE<T>& sample_t_ref_y = sample_t_ref[y]; VE<T> (&eval_y)[Y] = eval[y]; for(uint x = 0;x < Y;x++){ sample_t_ref_y[x] = eval_y[x][t]; } } } 
#define MULTIPLY_SUBPRODUCT_OF_PRECURSIVE_MATRIX(REST_INTERVAL_LENGTH) VE<MA<Y,Y,T> > eval_odd{}; VE<MA<Y,Y,T> > eval_even{}; SetIntervalEvaluation(subinterval_num_max,subinterval_length / interval_length,REST_INTERVAL_LENGTH + subinterval_num_max + 1,sample,eval_odd); SetIntervalEvaluation(subinterval_num_max,T(subinterval_num_max + 1),REST_INTERVAL_LENGTH,sample,eval_even); for(uint t = 0;t <= subinterval_num_max;t++){ sample[t] = move(eval_odd[t] * sample[t]); } for(uint t = 0;t < REST_INTERVAL_LENGTH;t++){ sample.push_back(move(eval_odd[t + subinterval_num_max + 1] * eval_even[t])); } 
#define PROD_MXK(K_START) FOR(k,K_START,K_lim){ MXk.push_front (move(MA<2,2,MODX> { X * CO_two - CO_two * k,X * k + CO_two_inv * ((1 - k) * k),one,zero })); }
IN CEXPR(ll,P,998244353);TE <ll M>class Mod{protected:ll m_n;ll m_inv;PU:IN Mod() NE;IN Mod(CO ll& n) NE;IN Mod(CO Mod<M>& n) NE;IN Mod<M>& OP=(CO ll& n) NE;Mod<M>& OP=(CO Mod<M>& n) NE;Mod<M>& OP+=(CO ll& n) NE;IN Mod<M>& OP+=(CO Mod<M>& n) NE;IN Mod<M>& OP-=(CO ll& n) NE;IN Mod<M>& OP-=(CO Mod<M>& n) NE;Mod<M>& OP*=(CO ll& n) NE;Mod<M>& OP*=(CO Mod<M>& n) NE;virtual Mod<M>& OP/=(CO ll& n);virtual Mod<M>& OP/=(CO Mod<M>& n);Mod<M>& OP%=(CO ll& 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 ll& Represent() CO NE;void Invert() NE;bool CheckInvertible() NE;bool IsSmallerThan(CO ll& n) CO NE;bool IsBiggerThan(CO ll& n) CO NE;};TE <ll M> IN bool OP==(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> IN bool OP==(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP==(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP==(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP!=(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> IN bool OP!=(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP!=(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP!=(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP<(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> IN bool OP<(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP<(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP<=(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> IN bool OP<=(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP<=(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP<=(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP>(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> IN bool OP>(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP>(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP>(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP>=(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> IN bool OP>=(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP>=(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP>=(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> Mod<M> OP+(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> Mod<M> OP+(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> Mod<M> OP+(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN Mod<M> OP-(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> Mod<M> OP-(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> Mod<M> OP-(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> Mod<M> OP*(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> Mod<M> OP*(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> Mod<M> OP*(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> Mod<M> OP/(CO Mod<M>& n0,CO ll& n1);TE <ll M> Mod<M> OP/(CO ll& n0,CO Mod<M>& n1);TE <ll M> Mod<M> OP/(CO Mod<M>& n0,CO Mod<M>& n1);TE <ll M> Mod<M> OP%(CO Mod<M>& n0,CO ll& n1);TE <ll M> IN Mod<M> OP%(CO ll& n0,CO Mod<M>& n1);TE <ll M> IN Mod<M> OP%(CO Mod<M>& n0,CO Mod<M>& n1);TE <ll M> Mod<M> Inverse(CO Mod<M>& n);TE <ll M> Mod<M> Power(CO Mod<M>& n,CO ll& p,CO string& method = "normal");TE <> IN Mod<2> Power(CO Mod<2>& n,CO ll& p,CO string& method);TE <ll 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 <ll M> IN string to_string(CO Mod<M>& n) NE;TE<ll M,class Traits> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO Mod<M>& n);void LazyEvaluationOfModularInverse(CO ll& M,CO ll& n,ll& m){CE CO ll border = 1000000;if(n > border){CO ll n_minus = M - n;if(n_minus <= border){LazyEvaluationOfModularInverse(M,n_minus,m);m = M - m;RE;} else {m = 1;ll exponent = M - 2;ll power_n = n;while(exponent != 0){if(exponent % 2 == 1){(m *= power_n) %= M;}(power_n *= power_n) %= M;exponent /= 2;}RE;}}ST LI<ll> memory_M{};ST LI<VE<ll> > memory_inverse{};auto I_M = memory_M.begin(),end_M = memory_M.end();auto I_inverse = memory_inverse.begin();VE<ll>* p_inverse = nullptr;while(I_M != end_M && p_inverse == nullptr){if(*I_M == M){p_inverse = &(*I_inverse);}I_M++;I_inverse++;}if(p_inverse == nullptr){memory_M.push_front(M);memory_inverse.push_front(VE<ll>());p_inverse = &(memory_inverse.front());p_inverse->push_back(M);}CO ll size = p_inverse->size();for(ll i = size;i <= n;i++){p_inverse->push_back(0);}ll& n_inv = (*p_inverse)[n];if(n_inv != 0){m = n_inv;RE;}CO ll M_abs = M >= 0 ? M:-M;CO ll n_sub = M_abs % n;ll 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(ll 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 <ll M> IN Mod<M>::Mod() NE:m_n(0),m_inv(M){}TE <ll M> IN Mod<M>::Mod(CO ll& n) NE:m_n(Residue<ll>(n,M)),m_inv(0){}TE <ll M> IN Mod<M>::Mod(CO Mod<M>& n) NE:m_n(n.m_n),m_inv(0){}TE <ll M> IN Mod<M>& Mod<M>::OP=(CO ll& n) NE { RE OP=(Mod<M>(n)); }TE <ll M>Mod<M>& Mod<M>::OP=(CO Mod<M>& n) NE{m_n = n.m_n;m_inv = n.m_inv;RE *this;}TE <ll M>Mod<M>& Mod<M>::OP+=(CO ll& n) NE{m_n = Residue<ll>(m_n + n,M);m_inv = 0;RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP+=(CO Mod<M>& n) NE { RE OP+=(n.m_n); };TE <ll M> IN Mod<M>& Mod<M>::OP-=(CO ll& n) NE { RE OP+=(-n); }TE <ll M> IN Mod<M>& Mod<M>::OP-=(CO Mod<M>& n) NE { RE OP-=(n.m_n); }TE <ll M>Mod<M>& Mod<M>::OP*=(CO ll& n) NE{m_n = Residue<ll>(m_n * n,M);m_inv = 0;RE *this;}TE <ll M>Mod<M>& Mod<M>::OP*=(CO Mod<M>& n) NE{m_n = Residue<ll>(m_n * n.m_n,M);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<ll>(m_inv * n.m_inv,M);}RE *this;}TE <ll M>Mod<M>& Mod<M>::OP/=(CO ll& n){RE OP/=(Mod<M>(n));}TE <ll M>Mod<M>& Mod<M>::OP/=(CO Mod<M>& n){RE OP*=(Inverse(n));}TE <ll M>Mod<M>& Mod<M>::OP%=(CO ll& n){m_n %= Residue<ll>(n,M);m_inv = 0;RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP%=(CO Mod<M>& n) { RE OP%=(n.m_n); }TE <ll M> IN Mod<M> Mod<M>::OP-() CO NE { RE Mod<M>(0).OP-=(*this); }TE <ll M> IN Mod<M>& Mod<M>::OP++() NE { RE OP+=(1); }TE <ll M> IN Mod<M>& Mod<M>::OP++(int) NE { RE OP++(); }TE <ll M> IN Mod<M>& Mod<M>::OP--() NE { RE OP-=(1); }TE <ll M> IN Mod<M>& Mod<M>::OP--(int) NE { RE OP-=(); }TE <ll M> IN CO ll& Mod<M>::Represent() CO NE { RE m_n; }TE <ll M>void Mod<M>::Invert() NE{if(CheckInvertible()){ll i = m_inv;m_inv = m_n;m_n = i;} else {m_n = M;m_inv = M;}RE;}TE <ll M>bool Mod<M>::CheckInvertible() NE{if(m_inv == 0){LazyEvaluationOfModularInverse(M,m_n,m_inv);}RE m_inv != M;}TE <ll M> IN bool Mod<M>::IsSmallerThan(CO ll& n) CO NE { RE m_n < Residue<ll>(n,M); }TE <ll M> IN bool Mod<M>::IsBiggerThan(CO ll& n) CO NE { RE m_n > Residue<ll>(n,M); }TE <ll M> IN bool OP==(CO Mod<M>& n0,CO ll& n1) NE { RE n0 == Mod<M>(n1); }TE <ll M> IN bool OP==(CO ll& n0,CO Mod<M>& n1) NE { RE Mod<M>(n0) == n0; }TE <ll M> IN bool OP==(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE n0.Represent() == n1.Represent(); }TE <ll M> IN bool OP!=(CO Mod<M>& n0,CO ll& n1) NE { RE !(n0 == n1); }TE <ll M> IN bool OP!=(CO ll& n0,CO Mod<M>& n1) NE { RE !(n0 == n1); }TE <ll M> IN bool OP!=(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE !(n0 == n1); }TE <ll M> IN bool OP<(CO Mod<M>& n0,CO ll& n1) NE { RE n0.IsSmallerThan(n1); }TE <ll M> IN bool OP<(CO ll& n0,CO Mod<M>& n1) NE { RE n1.IsBiggerThan(n0); }TE <ll M> IN bool OP<(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE n0.Represent() < n1.Represent(); }TE <ll M> IN bool OP<=(CO Mod<M>& n0,CO ll& n1) NE { RE !(n1 < n0); }TE <ll M> IN bool OP<=(CO ll& n0,CO Mod<M>& n1) NE { RE !(n1 < n0); }TE <ll M> IN bool OP<=(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE !(n1 < n0); }TE <ll M> IN bool OP>(CO Mod<M>& n0,CO ll& n1) NE { RE n1 < n0; }TE <ll M> IN bool OP>(CO ll& n0,CO Mod<M>& n1) NE { RE n1 < n0; }TE <ll M> IN bool OP>(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE n1 < n0; }TE <ll M> IN bool OP>=(CO Mod<M>& n0,CO ll& n1) NE { RE !(n0 < n1); }TE <ll M> IN bool OP>=(CO ll& n0,CO Mod<M>& n1) NE { RE !(n0 < n1); }TE <ll M> IN bool OP>=(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE !(n0 < n1); }TE <ll M>Mod<M> OP+(CO Mod<M>& n0,CO ll& n1) NE{auto n = n0;n += n1;RE n;}TE <ll M> IN Mod<M> OP+(CO ll& n0,CO Mod<M>& n1) NE { RE n1 + n0; }TE <ll M> IN Mod<M> OP+(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE n0 + n1.Represent(); }TE <ll M> IN Mod<M> OP-(CO Mod<M>& n0,CO ll& n1) NE { RE n0 + (-n1); }TE <ll M> IN Mod<M> OP-(CO ll& n0,CO Mod<M>& n1) NE { RE Mod<M>(n0 - n1.Represent()); }TE <ll M> IN Mod<M> OP-(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE n0 - n1.Represent(); }TE <ll M>Mod<M> OP*(CO Mod<M>& n0,CO ll& n1) NE{auto n = n0;n *= n1;RE n;}TE <ll M> IN Mod<M> OP*(CO ll& n0,CO Mod<M>& n1) NE { RE n1 * n0; }TE <ll M>Mod<M> OP*(CO Mod<M>& n0,CO Mod<M>& n1) NE{auto n = n0;n *= n1;RE n;}TE <ll M> IN Mod<M> OP/(CO Mod<M>& n0,CO ll& n1) { RE n0 / Mod<M>(n1); }TE <ll M> IN Mod<M> OP/(CO ll& n0,CO Mod<M>& n1) { RE Mod<M>(n0) / n1; }TE <ll M>Mod<M> OP/(CO Mod<M>& n0,CO Mod<M>& n1){auto n = n0;n /= n1;RE n;}TE <ll M>Mod<M> OP%(CO Mod<M>& n0,CO ll& n1){auto n = n0;n %= n1;RE n;}TE <ll M> IN Mod<M> OP%(CO ll& n0,CO Mod<M>& n1) { RE Mod<M>(n0) % n1.Represent(); }TE <ll M> IN Mod<M> OP%(CO Mod<M>& n0,CO Mod<M>& n1) { RE n0 % n1.Represent(); }TE <ll M>Mod<M> Inverse(CO Mod<M>& n){auto n_copy = n;n_copy.Invert();RE n_copy;}TE <ll M>Mod<M> Power(CO Mod<M>& n,CO ll& p,CO string& method){if(p >= 0){RE Power<Mod<M>,ll>(n,p,1,true,true,method);}RE Inverse(Power<M>(n,-p,method));}TE <> IN Mod<2> Power(CO Mod<2>& n,CO ll& p,CO string& method) { RE p == 0 ? 1:n; }TE <ll M> IN Mod<M> Power(CO Mod<M>& n,CO Mod<M>& p,CO string& method) { RE Power<Mod<M>,ll>(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 <ll M> IN string to_string(CO Mod<M>& n) NE { RE to_string(n.Represent()) + " + MZ"; }TE<ll M,class Traits> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO Mod<M>& n) { RE os << n.Represent(); }TE <TY T> class TRPO;TE <TY T>class PO{friend class TRPO<T>;protected:VE<T> m_f;uint m_size;PU:IN PO();IN PO(CO T& t);IN PO(CO PO<T>& f);IN PO(PO<T>&& f);IN PO(CO uint& 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[](CO uint& i) CO;IN T& OP[](CO uint& i);IN T OP()(CO T& t) CO;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 PO<T>& f);PO<T>& OP%=(CO T& t);PO<T>& OP%=(CO PO<T>& f);IN PO<T> OP-() CO;PO<T>& OP<<=(CO T& t);IN CO VE<T>& GetCoefficient() CO NE;IN CO uint& size() CO NE;IN void swap(PO<T>& f);IN void swap(VE<T>& f);void RemoveRedundantZero();IN string Display() CO NE;ST IN CO PO<T>& zero();ST IN CO T& CO_zero();ST IN CO T& CO_one();ST IN CO T& CO_minus_one();ST IN CO T& factorial(CO uint& i);ST IN CO T& factorial_inverse(CO uint& i);};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,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>& f,CO T& t);TE <TY T> IN T& Prod(LI<T>& f);TE <TY T> class TRPO;TE <TY T> TRPO<T> TRDifferential(CO TRPO<T>& f,CO uint& N_OPT_start_plus_one);TE <TY T> TRPO<T> TRIntegral(CO TRPO<T>& f,CO uint& N_OPT_start);TE <TY T> class TRPO;TE <TY T> TRPO<T> TRDifferential(CO TRPO<T>& f,CO uint& N_OPT_start_plus_one);TE <TY T> TRPO<T> TRIntegral(CO TRPO<T>& f,CO uint& N_OPT_start);TE <TY T>class TRPO :PU PO<T>{friend TRPO<T> TRDifferential<T>(CO TRPO<T>& f,CO uint& N_OPT_start_plus_one);friend TRPO<T> TRIntegral<T>(CO TRPO<T>& f,CO uint& N_OPT_start);PR:uint m_N;PU:IN TRPO(CO uint& N = 0);IN TRPO(CO TRPO<T>& f);IN TRPO(CO uint& N,CO T& t);TRPO(CO uint& N,CO PO<T>& f);IN TRPO(CO uint& N,PO<T>&& f);IN TRPO(CO uint& N,CO uint& i,CO T& t);IN TRPO(CO uint& 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);IN TRPO<T>& OP+=(CO TRPO<T>& f);TRPO<T>& TRPlus(CO PO<T>& f,CO uint& N_IPT_start,CO uint& N_IPT_limit);IN TRPO<T>& OP-=(CO T& t);IN TRPO<T>& OP-=(CO PO<T>& f);IN TRPO<T>& OP-=(CO TRPO<T>& f);TRPO<T>& TRMinus(CO PO<T>& f,CO uint& N_IPT_start,CO uint& N_IPT_limit);IN TRPO<T>& OP*=(CO T& t);TRPO<T>& OP*=(CO PO<T>& f);TRPO<T>& FFT_MU(CO PO<T>& f);TRPO<T>& TRMU(CO PO<T>& f,CO uint& N_IPT_start,CO uint& N_IPT_lim);TRPO<T>& FFT_TRMU(CO PO<T>& f,CO uint& N_IPT_start,CO uint& N_IPT_lim);TRPO<T> TRMU_CO(CO PO<T>& f,CO uint& N_OPT_start,CO uint& N_OPT_lim) CO;TRPO<T> FFT_TRMU_CO(CO PO<T>& f,CO uint& N_OPT_start,CO uint& N_OPT_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(CO uint& N) NE;IN CO uint& GetTruncation() CO NE;IN TRPO<T>& TruncateInitial(CO uint& N) NE;IN TRPO<T>& TruncateFinal(CO uint& N) NE;};TE <TY T> IN CE CO uint FFT_MU_border_0;TE <TY T> IN CE CO uint FFT_MU_border_1;TE <TY T> IN CE CO uint FFT_MU_border_1_2;TE <TY T> IN CE CO uint FFT_MU_border_1_2_exponent;TE <TY T> IN CE CO uint FFT_MU_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(CO uint& i,CO TRPO<T>& f);TE <TY T> TRPO<T> TRDifferential(CO TRPO<T>& f,CO uint& N_OPT_start_plus_one);TE <TY T> IN TRPO<T> Integral(CO TRPO<T>& f);TE <TY T>TRPO<T> TRIntegral(CO TRPO<T>& f,CO uint& N_OPT_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 CE CO uint LimitOfPowerForFFT;TE <TY T> IN CE 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,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& two_power,CO uint& exponent);TE <TY T> IN VE<T> FFT(CO VE<T>& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& N_OPT_start,CO uint& N_OPT_lim,CO uint& N_OPT_shift,CO uint& two_power,CO uint& exponent);TE <TY T> VE<T> IFFT(CO VE<T>& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& two_power,CO T& two_power_inv,CO uint& exponent);TE <TY T> VE<T> IFFT(CO VE<T>& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& N_OPT_start,CO uint& N_OPT_lim,CO uint& N_OPT_shift,CO uint& two_power,CO T& two_power_inv,CO uint& exponent);TE <> IN CE CO uint LimitOfPowerForFFT<Mod<P> > = 24;TE <> IN CE CO uint BorderForFFT<Mod<P> > = 4; TE <> IN CO Mod<P> (&PrimitiveRootOfTwoForFFT() NE)[LimitOfPowerForFFT<Mod<P> >]{ST CO Mod<P> PRT[ LimitOfPowerForFFT<Mod<P> > ] ={Mod<P>(1) ,Mod<P>(998244352) ,Mod<P>(911660635) ,Mod<P>(625715529) ,Mod<P>(373294451) ,Mod<P>(827987769) ,Mod<P>(280333251) ,Mod<P>(581015842) ,Mod<P>(628092333) ,Mod<P>(300892551) ,Mod<P>(586046298) ,Mod<P>(615001099) ,Mod<P>(318017948) ,Mod<P>(64341522) ,Mod<P>(106061068) ,Mod<P>(304605202) ,Mod<P>(631920086) ,Mod<P>(857779016) ,Mod<P>(841431251) ,Mod<P>(805775211) ,Mod<P>(390359979) ,Mod<P>(923521) ,Mod<P>(961) ,Mod<P>(31)};RE PRT;}TE <> IN CO Mod<P> (&InversePrimitiveRootOfTwoForFFT() NE)[LimitOfPowerForFFT<Mod<P> >]{ST CO Mod<P> PRT[ LimitOfPowerForFFT<Mod<P> > ] ={Mod<P>(1) ,Mod<P>(998244352) ,Mod<P>(86583718) ,Mod<P>(488723995) ,Mod<P>(369330050) ,Mod<P>(543653592) ,Mod<P>(382946991) ,Mod<P>(844956623) ,Mod<P>(91420391) ,Mod<P>(433414612) ,Mod<P>(288894979) ,Mod<P>(260490556) ,Mod<P>(857007890) ,Mod<P>(736054570) ,Mod<P>(474649464) ,Mod<P>(948509906) ,Mod<P>(114942468) ,Mod<P>(962405921) ,Mod<P>(667573957) ,Mod<P>(46809892) ,Mod<P>(304321983) ,Mod<P>(30429817) ,Mod<P>(293967900) ,Mod<P>(128805723)};RE PRT;}TE <TY T>ST VE<T> FFT_Body(CO VE<T>& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& N_OPT_start,CO uint& N_OPT_lim,CO uint& N_OPT_shift,CO uint& two_power,CO uint& exponent,CO T (&PRT)[LimitOfPowerForFFT<T>]);TE <TY T>ST VE<T> FFT_Body(CO VE<T>& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& two_power,CO uint& exponent,CO uint& start,CO uint& depth,CO T (&PRT)[LimitOfPowerForFFT<T>]);TE <TY T> IN VE<T> FFT(CO VE<T>& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& two_power,CO uint& exponent) { RE FFT_Body<T>(f,N_IPT_start,N_IPT_lim,N_IPT_shift,two_power,exponent,0,1,PrimitiveRootOfTwoForFFT<T>()); }TE <TY T> IN VE<T> FFT(CO VE<T>& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& N_OPT_start,CO uint& N_OPT_lim,CO uint& N_OPT_shift,CO uint& two_power,CO uint& exponent) { RE FFT_Body<T>(f,N_IPT_start,N_IPT_lim,N_IPT_shift,N_OPT_start,N_OPT_lim,N_OPT_shift,two_power,exponent,PrimitiveRootOfTwoForFFT<T>()); }TE <TY T>VE<T> IFFT(CO VE<T>& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& two_power,CO T& two_power_inv,CO uint& exponent){VE<T> answer{ move(FFT_Body<T>(f,N_IPT_start,N_IPT_lim,N_IPT_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,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& N_OPT_start,CO uint& N_OPT_lim,CO uint& N_OPT_shift,CO uint& two_power,CO T& two_power_inv,CO uint& exponent){VE<T> answer{ move(FFT_Body<T>(f,N_IPT_start,N_IPT_lim,N_IPT_shift,N_OPT_start,N_OPT_lim,N_OPT_shift,two_power,exponent,InversePrimitiveRootOfTwoForFFT<T>())) };uint size = answer.size();CO uint N_OPT_length = N_OPT_lim - N_OPT_start + N_OPT_shift;if(size < N_OPT_length){size = N_OPT_length;}for(uint i = N_OPT_shift;i < size;i++){answer[i] *= two_power_inv;}RE answer;}TE <TY T>ST VE<T> FFT_Body(CO VE<T>& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& N_OPT_start,CO uint& N_OPT_lim,CO uint& N_OPT_shift,CO uint& two_power,CO uint& exponent,CO T (&PRT)[LimitOfPowerForFFT<T>]){CO uint length = N_OPT_lim - N_OPT_start + N_OPT_shift;VE<T> answer(length);if(two_power == 1){if(N_IPT_shift == 0 && N_OPT_shift < length){if(N_IPT_start < N_IPT_lim){answer[N_OPT_shift] = f[N_IPT_start];}}} else {CO T& zeta = PRT[exponent];T zeta_power = PRT[0];uint N_OPT_start_copy = N_OPT_start;uint digit = 0;if(N_OPT_start_copy != 0){if(N_OPT_start_copy % 2 == 1){zeta_power *= zeta;}N_OPT_start_copy /= 2;digit++;}while(N_OPT_start_copy != 0){if(N_OPT_start_copy % 2 == 1){zeta_power *= PRT[exponent - digit];}N_OPT_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_IPT_start,N_IPT_lim,N_IPT_shift,two_power_sub,exponent_sub,0,2,PRT)) };VE<T> answer_sub1{ move(FFT_Body<T>(f,N_IPT_start,N_IPT_lim,N_IPT_shift,two_power_sub,exponent_sub,1,2,PRT)) };for(uint i = N_OPT_start;i < N_OPT_lim;i++){CO uint i_sub = i % two_power_sub;answer[i - N_OPT_start + N_OPT_shift] = answer_sub0[i_sub] + zeta_power * answer_sub1[i_sub];zeta_power *= zeta;}}RE answer;}TE <TY T>ST VE<T> FFT_Body(CO VE<T>& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& two_power,CO uint& exponent,CO uint& start,CO uint& depth,CO T (&PRT)[LimitOfPowerForFFT<T>]){VE<T> answer(two_power);CO uint start_depth = start + ((two_power - 1) * depth);CO uint N_IPT_length = N_IPT_lim - N_IPT_start + N_IPT_shift;if(start < N_IPT_length && N_IPT_shift <= start_depth){uint j_min;if(start < N_IPT_shift){CO uint N_IPT_shift_shift = N_IPT_shift - start;j_min = N_IPT_shift_shift / depth + (N_IPT_shift_shift % depth == 0 ? 0:1);} else {j_min = 0;}uint j_lim;if(N_IPT_length <= start_depth){CO uint N_IPT_length_shift = N_IPT_length - start;j_lim = N_IPT_length_shift / depth + (N_IPT_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_IPT_shift + N_IPT_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 };CE CO uint& 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_IPT_shift + N_IPT_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_IPT_start,N_IPT_lim,N_IPT_shift,two_power_sub,exponent_sub,start,depth_sub,PRT)) };VE<T> answer_sub1{ move(FFT_Body<T>(f,N_IPT_start,N_IPT_lim,N_IPT_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> IN TRPO<T>::TRPO(CO uint& 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(CO uint& N,CO T& t):PO<T>(t),m_N(N) {}TE <TY T>TRPO<T>::TRPO(CO uint& 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(CO uint& N,PO<T>&& f):PO<T>(move(f)),m_N(N) {};TE <TY T> IN TRPO<T>::TRPO(CO uint& N,CO uint& i,CO T& t):PO<T>(),m_N(N) { if(i < m_N ? t != PO<T>::CO_zero():false){ PO<T>::OP[](i) = t; } }TE <TY T> IN TRPO<T>::TRPO(CO uint& 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> IN TRPO<T>& TRPO<T>::OP+=(CO TRPO<T>& f) { RE m_N == 0 ? OP=(f):TRPO<T>::TRPlus(f,0,f.PO<T>::m_size); }TE <TY T>TRPO<T>& TRPO<T>::TRPlus(CO PO<T>& f,CO uint& N_OPT_start,CO uint& N_OPT_limit){CO uint& size = N_OPT_limit < m_N ? N_OPT_limit < f.PO<T>::m_size ? N_OPT_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_OPT_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> IN TRPO<T>& TRPO<T>::OP-=(CO TRPO<T>& f) { RE m_N == 0 ? OP=(-f):TRPO<T>::TRMinus(f,0,f.PO<T>::m_size); }TE <TY T>TRPO<T>& TRPO<T>::TRMinus(CO PO<T>& f,CO uint& N_OPT_start,CO uint& N_OPT_limit){CO uint& size = N_OPT_limit < m_N ? N_OPT_limit < f.PO<T>::m_size ? N_OPT_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_OPT_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; }DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_TR_PO(Mod<P>,12,512,1024,10,997269505); TE <TY T>TRPO<T>& TRPO<T>::OP*=(CO PO<T>& f){CE CO uint border_0 = 21;CO T& zero = PO<T>::CO_zero();bool SE = true;if(PO<T>::m_size < border_0 && f.PO<T>::m_size < border_0){RE_ZR_FOR_MU_FOR_TR_PO_IF(f.PO<T>::m_size == 0);DF_0_OF_MU_FOR_TR_PO;} else {DF_1_OF_MU_FOR_TR_PO;RE_ZR_FOR_MU_FOR_TR_PO_IF(SE);DF_2_OF_MU_FOR_TR_PO;CO uint N_OPT_lim_fixed = N_IPT_max_0_max_1 < m_N ? N_IPT_max_0_max_1 + 1:m_N;RE_ZR_FOR_MU_FOR_TR_PO_IF(N_IPT_start_0_start_1 >= m_N);DF_3_OF_MU_FOR_TR_PO;}RE *this;}TE <TY T>TRPO<T>& TRPO<T>::FFT_MU(CO PO<T>& f){CE CO uint& border_0 = FFT_MU_border_0<T>;CO T& zero = PO<T>::CO_zero();bool SE = true;if(PO<T>::m_size < border_0 && f.PO<T>::m_size < border_0){RE_ZR_FOR_MU_FOR_TR_PO_IF(f.PO<T>::m_size == 0);DF_0_OF_MU_FOR_TR_PO;} else {DF_1_OF_MU_FOR_TR_PO;RE_ZR_FOR_MU_FOR_TR_PO_IF(SE);DF_2_OF_MU_FOR_TR_PO;CO uint N_OPT_lim_fixed = N_IPT_max_0_max_1 < m_N ? N_IPT_max_0_max_1 + 1:m_N;RE_ZR_FOR_MU_FOR_TR_PO_IF(N_IPT_start_0_start_1 >= N_OPT_lim_fixed);CO uint N_IPT_truncated_deg_0_deg_1 = N_IPT_max_0 - N_IPT_start_0 + N_IPT_max_1 - N_IPT_start_1;CE CO uint& border_1 = FFT_MU_border_1<T>;if(N_IPT_truncated_deg_0_deg_1 < border_1){DF_3_OF_MU_FOR_TR_PO;} else {DF_4_OF_MU_FOR_TR_PO;PO<T>::m_f = move(IFFT<T>(f0,0,two_power,0,0,N_OPT_lim_fixed - N_IPT_start_0_start_1,N_IPT_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>::TRMU(CO PO<T>& f,CO uint& N_OPT_start,CO uint& N_OPT_lim){CE CO uint border_0 = 21;CO T& zero = PO<T>::CO_zero();bool SE = true;if(PO<T>::m_size < border_0 && f.PO<T>::m_size < border_0){DF_0_OF_MU_FOR_TR_PO;} else {DF_1_OF_MU_FOR_TR_PO;DF_2_OF_MU_FOR_TR_PO;uint N_OPT_lim_fixed = N_IPT_max_0_max_1 < m_N ? N_IPT_max_0_max_1 + 1:m_N;if(N_OPT_lim_fixed > N_OPT_lim){N_OPT_lim_fixed = N_OPT_lim;}RE_ZR_FOR_MU_FOR_TR_PO_IF(N_IPT_start_0_start_1 >= N_OPT_lim_fixed);DF_3_OF_MU_FOR_TR_PO;}RE *this;}TE <TY T> TRPO<T>& TRPO<T>::FFT_TRMU(CO PO<T>& f,CO uint& N_OPT_start,CO uint& N_OPT_lim){CE CO uint& border_0 = FFT_MU_border_0<T>;CO T& zero = PO<T>::CO_zero();bool SE = true;if(PO<T>::m_size < border_0 && f.PO<T>::m_size < border_0){DF_0_OF_MU_FOR_TR_PO;} else {DF_1_OF_MU_FOR_TR_PO;DF_2_OF_MU_FOR_TR_PO;uint N_OPT_lim_fixed = N_IPT_max_0_max_1 < m_N ? N_IPT_max_0_max_1 + 1:m_N;if(N_OPT_lim_fixed > N_OPT_lim){N_OPT_lim_fixed = N_OPT_lim;}RE_ZR_FOR_MU_FOR_TR_PO_IF(N_IPT_start_0_start_1 >= N_OPT_lim_fixed);CO uint N_IPT_truncated_deg_0_deg_1 = N_IPT_max_0 - N_IPT_start_0 + N_IPT_max_1 - N_IPT_start_1;CE CO uint& border_1 = FFT_MU_border_1<T>;if(N_IPT_truncated_deg_0_deg_1 < border_1){DF_3_OF_MU_FOR_TR_PO;} else {DF_4_OF_MU_FOR_TR_PO;uint N_OPT_start_shifted;uint N_OPT_shift_shifted;if(N_OPT_start < N_IPT_start_0_start_1){N_OPT_start_shifted = 0;N_OPT_shift_shifted = N_IPT_start_0_start_1;} else {N_OPT_start_shifted = N_OPT_start - N_IPT_start_0_start_1;N_OPT_shift_shifted = N_OPT_start;}CO uint N_OPT_lim_shifted = N_OPT_lim_fixed - N_IPT_start_0_start_1;f0 = move(IFFT<T>(f0,0,two_power,0,N_OPT_start_shifted,N_OPT_lim_shifted,N_OPT_shift_shifted,two_power,two_power_inv,exponent));SET_VE_FOR_AN_OF_MU_FOR_TR_PO(N_OPT_lim_fixed);for(uint i = N_OPT_start;i < N_OPT_lim_fixed;i++){PO<T>::m_f[i] = f0[i];}}}RE *this;}TE <TY T> TRPO<T> TRPO<T>::TRMU_CO(CO PO<T>& f,CO uint& N_OPT_start,CO uint& N_OPT_lim) CO{CE CO uint border_0 = 21;CO T& zero = PO<T>::CO_zero();bool SE = true;if(PO<T>::m_size < border_0 && f.PO<T>::m_size < border_0){DF_0_OF_TR_MU_CO_FOR_TR_PO;RE TRPO<T>(m_N,move(answer));}DF_1_OF_TR_MU_CO_FOR_TR_PO;DF_2_OF_TR_MU_CO_FOR_TR_PO;uint N_OPT_lim_fixed = N_IPT_max_0_max_1 < m_N ? N_IPT_max_0_max_1 + 1:m_N;if(N_OPT_lim_fixed > N_OPT_lim){N_OPT_lim_fixed = N_OPT_lim;}RE_ZR_FOR_TR_MU_CO_FOR_TR_PO_IF(N_IPT_start_0_start_1 >= N_OPT_lim_fixed);DF_3_OF_TR_MU_CO_FOR_TR_PO;RE TRPO<T>(m_N,move(answer));}TE <TY T> TRPO<T> TRPO<T>::FFT_TRMU_CO(CO PO<T>& f,CO uint& N_OPT_start,CO uint& N_OPT_lim) CO{CE CO uint& border_0 = FFT_MU_border_0<T>;CO T& zero = PO<T>::CO_zero();bool SE = true;if(PO<T>::m_size < border_0 && f.PO<T>::m_size < border_0){DF_0_OF_TR_MU_CO_FOR_TR_PO;RE TRPO<T>(m_N,move(answer));}DF_1_OF_TR_MU_CO_FOR_TR_PO;DF_2_OF_TR_MU_CO_FOR_TR_PO;uint N_OPT_lim_fixed = N_IPT_max_0_max_1 < m_N ? N_IPT_max_0_max_1 + 1:m_N;if(N_OPT_lim_fixed > N_OPT_lim){N_OPT_lim_fixed = N_OPT_lim;}RE_ZR_FOR_TR_MU_CO_FOR_TR_PO_IF(N_IPT_start_0_start_1 >= N_OPT_lim_fixed);CO uint N_IPT_truncated_deg_0_deg_1 = N_IPT_max_0 - N_IPT_start_0 + N_IPT_max_1 - N_IPT_start_1;CE CO uint& border_1 = FFT_MU_border_1<T>;if(N_IPT_truncated_deg_0_deg_1 < border_1){DF_3_OF_TR_MU_CO_FOR_TR_PO;RE TRPO<T>(m_N,move(answer));}DF_4_OF_TR_MU_CO_FOR_TR_PO;uint N_OPT_start_shifted;uint N_OPT_shift_shifted;if(N_OPT_start < N_IPT_start_0_start_1){N_OPT_start_shifted = 0;N_OPT_shift_shifted = N_IPT_start_0_start_1;} else {N_OPT_start_shifted = N_OPT_start - N_IPT_start_0_start_1;N_OPT_shift_shifted = N_OPT_start;}CO uint N_OPT_lim_shifted = N_OPT_lim_fixed - N_IPT_start_0_start_1;RE TRPO<T>(m_N,move(IFFT<T>(f0,0,two_power,0,N_OPT_start_shifted,N_OPT_lim_shifted,N_OPT_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(CO uint& 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(CO uint& N) NE { CO uint& 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(CO uint& 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>::CO_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(CO uint& 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,CO uint& N_OPT_start_plus_one){if(f.m_N == 0){RE TRPO<T>();}TRPO<T> f_dif{ f.m_N - 1 };if(N_OPT_start_plus_one < f.PO<T>::m_size){for(uint i = 1;i < N_OPT_start_plus_one;i++){f_dif.PO<T>::m_f.push_back(0);}for(uint i = N_OPT_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,CO uint& N_OPT_start){TRPO<T> f_int{ f.m_N + 1 };if(N_OPT_start <= f.PO<T>::m_size){for(uint i = 0;i < N_OPT_start;i++){f_int.PO<T>::m_f.push_back(0);}for(uint i = N_OPT_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){DF_OF_INVERSE_FOR_TR_PO(T,f_inv.TRMinus(f_inv.TRMU_CO(f,power,power_2).TRMU(f_inv,power,power_2),power,power_2));}TE <TY T>TRPO<T> Exp(CO TRPO<T>& f){DF_OF_EXP_FOR_TR_PO(T,f_exp.TRMinus((TRIntegral(Differential(f_exp).TRMU_CO(Inverse(f_exp),power - 1,power_2),power).TRMinus(f,power,power_2)).TRMU(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); }TE <TY T> IN PO<T>::PO():m_f(),m_size(0) {}TE <TY T> IN PO<T>::PO(CO T& t):PO() { if(t != CO_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) {}TE <TY T> IN PO<T>::PO(PO<T>&& f):m_f(move(f.m_f)),m_size(move(f.m_size)) {}TE <TY T> IN PO<T>::PO(CO uint& i,CO T& t):PO() { if(t != CO_zero()){ OP[](i) = t; } }TE <TY T> IN PO<T>::PO(VE<T>&& f):m_f(move(f)),m_size(m_f.size()) {}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; RE *this; }TE <TY T>CO T& PO<T>::OP[](CO uint& i) CO{if(m_size <= i){RE CO_zero();}RE m_f[i];}TE <TY T> IN T& PO<T>::OP[](CO uint& i){if(m_size <= i){CO T& z = CO_zero();while(m_size <= i){m_f.push_back(z);m_size++;}}RE m_f[i];}TE <TY T> IN T PO<T>::OP()(CO T& t) CO { RE (*this % (PO<T>(1,CO_one()) - t))[0]; }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;}DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(Mod<P>);TE <TY T>PO<T>& PO<T>::OP*=(CO T& t){if(m_size == 0 || t == CO_one()){RE *this;}if(t == CO_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=(move(product));}TE <TY T>PO<T>& PO<T>::OP/=(CO T& t){if(t == CO_one()){RE *this;}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 >= f.m_size){assert(f.m_size > 0);uint size0 = m_size - f.m_size + 1;TRPO<T> f0_copy(size0);for(uint d0 = 0;d0 < size0;d0++){f0_copy.PO<T>::m_f.push_back(m_f[m_size - 1 - d0]);}f0_copy.PO<T>::m_size = size0;TRPO<T> f1_copy(size0);uint size1 = size0 < f.m_size ? size0:f.m_size;for(uint d1 = 0;d1 < size1;d1++){f1_copy.PO<T>::m_f.push_back(f.m_f[f.m_size - 1 - d1]);}f1_copy.PO<T>::m_size = size1;f0_copy /= f1_copy;for(uint d0 = 0;d0 < size0;d0++){m_f[d0] = f0_copy[ size0 - 1 - d0 ];}while(m_size > size0){m_f.pop_back();m_size--;}} else {PO<T>::m_f.clear();PO<T>::m_size = 0;}RE *this;}TE <TY T>PO<T>& PO<T>::OP%=(CO T& t){if(t == CO_one()){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 >= f.m_size){OP-=((*this / f) * f);RemoveRedundantZero();}RE *this;}TE <TY T> IN PO<T> PO<T>::OP-() CO { RE PO<T>().OP-=(*this); }TE <TY T >PO<T>& PO<T>::OP<<=(CO T& t){if(m_size > 0){ST T factorial_curr = 1;ST VE<T> factorial = { 1,1 };ST T factorial_inv_curr = 1;ST VE<T> factorial_inv = { 1,1 };uint size = factorial.size();while(size < m_size){factorial.push_back(factorial_curr *= size);factorial_inv.push_back(factorial_inv_curr /= size);size++;}for(uint d = 0;d < m_size;d++){m_f[d] *= factorial[d];}TRPO<T> f{ m_size * 2 };T power_t = CO_one();for(uint d = 0;d < m_size;d++){f[m_size - 1 - d] = power_t * factorial_inv[d];power_t *= t;}f *= *this;for(uint d = 0;d < m_size;d++){m_f[d] = f.PO<T>::m_f[d + m_size - 1] * factorial_inv[d];}}RE *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> IN void PO<T>::swap(PO<T>& f) { m_f.swap(f.m_f); swap(m_size,f.m_size); }TE <TY T> IN void PO<T>::swap(VE<T>& f) { m_f.swap(f); m_size = m_f.size(); }TE <TY T>void PO<T>::RemoveRedundantZero(){CO T& z = CO_zero();while(m_size > 0 ? m_f[m_size - 1] == z:false){m_f.pop_back();m_size--;}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() { ST CO PO<T> z{}; RE z; }TE <TY T> IN CO T& PO<T>::CO_zero() { ST CO T z{ 0 }; RE z; }TE <TY T> IN CO T& PO<T>::CO_one() { ST CO T o{ 1 }; RE o; }TE <TY T> IN CO T& PO<T>::CO_minus_one() { ST CO T m{ -1 }; RE m; }TE <TY T> IN CO T& PO<T>::factorial(CO uint& i) { ST VE<T> memory = { CO_one(),CO_one() }; ST T curr = CO_one(); ST uint size = 2; while(size <= i){ memory.push_back(curr *= size++); } RE memory[i]; }TE <TY T> IN CO T& PO<T>::factorial_inverse(CO uint& i) { ST VE<T> memory = { CO_one(),CO_one() }; ST T curr = CO_one(); ST uint size = 2; while(size <= i){ memory.push_back(curr /= size++); } RE memory[i]; }TE <TY T>bool OP==(CO PO<T>& f0,CO T& t1){CO uint& size = f0.size();CO T& zero = PO<T>::CO_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 operator!=(CO PO<T>& f0,CO P& f1) { RE !(f0 == f1); }TE <TY T,TY P> IN PO<T> operator+(CO PO<T>& f0,CO P& f1) { PO<T> f = f0; f += f1; RE f; }TE <TY T,TY P> IN PO<T> operator-(CO PO<T>& f) { RE PO<T>::zero() - f; }TE <TY T,TY P> IN PO<T> operator-(CO PO<T>& f0,CO P& f1) { PO<T> f = f0; RE f.operator-=(f1); }TE <TY T,TY P> IN PO<T> operator*(CO PO<T>& f0,CO P& f1) { PO<T> f = f0; RE f.operator*=(f1); }TE <TY T,TY P> IN PO<T> operator/(CO PO<T>& f0,CO P& f1) { PO<T> f = f0; RE f.operator/=(f1); }TE <TY T,TY P> IN PO<T> operator%(CO PO<T>& f0,CO P& f1) { PO<T> f = f0; RE f.operator%=(f1); }TE <TY T> PO<T> operator<<(CO PO<T>& f,CO T& t) { RE PO<T>(f) <<= t; };TE <TY T> IN T& Prod(LI<T>& f){if(f.empty()){f.push_back(T(1));}if(f.size() == 1){RE f.front();}auto I = f.begin(),end = f.end();while(I != end){T& t = *I;I++;if(I != end){t = t * *I;I = f.erase(I);}}RE Prod(f);}TE <TY T,TY V> IN void SetMultipointEvaluation(CO PO<T>& f,CO V& point,V& answer);TE <TY T,TY V>void SetMultipointEvaluation(CO PO<T>& f,CO LI<LI<PO<T> > >& point_tree,V& answer);TE <TY T> IN void SetMultipointEvaluation(CO PO<T>& f,CO LI<T>& point,LI<T>& answer);TE <TY T>void SetProductTree(LI<LI<T> >& product_tree);TE <TY T,TY V>void SetPointTree(CO V& point,LI<LI<PO<T> > >& point_tree);TE <TY T,TY V> IN void SetMultipointEvaluation(CO PO<T>& f,CO V& point,V& answer) { LI<LI<PO<T> > > pt{}; SetPointTree(point,pt); SetMultipointEvaluation(f,pt,answer); }TE <TY T,TY V>void SetMultipointEvaluation(CO PO<T>& f,CO LI<LI<PO<T> > >& point_tree,V& answer){CO LI<PO<T> >& prod = point_tree.front();if(prod.empty()){RE;}LI<PO<T> > residue = {};CO PO<T>& zero = PO<T>::zero();residue.push_back(zero);residue.back() = move(f % prod.front());auto I_tree = point_tree.begin(),end_tree = point_tree.end();I_tree++;while(I_tree != end_tree){auto I_residue = residue.begin(),end_residue = residue.end();auto I_node = I_tree->begin(),end_node = I_tree->end();while(I_residue != end_residue){CO PO<T>& f = *I_node;I_node++;if(I_node != end_node){*(residue.insert(I_residue,zero)) = move(*I_residue % f);*I_residue %= *I_node;I_node++;}I_residue++;}I_tree++;}for(auto I_residue = residue.begin(),end_residue = residue.end();I_residue != end_residue;I_residue++){answer.push_back((*I_residue)[0]);}RE;}TE <TY T>void SetProductTree(LI<LI<T> >& product_tree){LI<T> empty{};LI<T> *p_node = &(product_tree.back());while(p_node->size() > 1){product_tree.push_front(empty);LI<T>& node_curr = product_tree.front();for(auto I = p_node->begin(),end = p_node->end();I != end;I++){ST CO T null{};node_curr.push_back(null);T& f = *I;I++;if(I == end){node_curr.back() = f;break;} else {node_curr.back() = move(f * *I);}}p_node = &node_curr;}RE;}TE <TY T,TY V>void SetPointTree(CO V& point,LI<LI<PO<T> > >& point_tree){ST CO LI<PO<T> > empty{};point_tree.push_front(empty);LI<PO<T> >& linear = point_tree.front();for(auto I = point.begin(),end = point.end();I != end;I++){ST CO PO<T> x{ 1,PO<T>::CO_one() };linear.push_back(x);linear.back()[0] -= *I;}SetProductTree(point_tree);RE;}TE <TY T>using TableTypeForMA = VE<VE<T> >;TE <uint Y,uint X,TY T>class MA{PR:TableTypeForMA<T> m_M;PU:IN MA(CO T& t) NE;IN MA(CO int& t) NE;TE <TY... Args> MA(CO Args&... args) NE;IN MA(CO MA<Y,X,T>& mat) NE;IN MA(MA<Y,X,T>&& mat) NE;TE <TY... Args> IN MA(CO TableTypeForMA<T>& M) NE;TE <TY... Args> IN MA(TableTypeForMA<T>&& M) NE;IN MA<Y,X,T>& operator=(CO MA<Y,X,T>& mat) NE;MA<Y,X,T>& operator+=(CO MA<Y,X,T>& mat);MA<Y,X,T>& operator-=(CO MA<Y,X,T>& mat);MA<Y,X,T>& operator*=(CO T& scalar) NE;IN MA<Y,X,T>& operator*=(CO MA<X,X,T>& mat) NE;MA<Y,X,T>& operator%=(CO T& scalar) NE;IN TableTypeForMA<T>& RefTable() NE;IN CO TableTypeForMA<T>& GetTable() CO NE;ST IN CO MA<Y,X,T>& Zero() NE;ST IN CO MA<Y,X,T>& Unit() NE;ST MA<Y,X,T> Scalar(CO T& t) NE;PR:ST IN void COructTable(TableTypeForMA<T>& M,VE<T>& vec) NE;TE <TY... Args> ST void COructTable(TableTypeForMA<T>& M,VE<T>& vec,CO T& t,CO Args&... args) NE;ST MA<Y,X,T> Zero_Body() NE;};TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator==(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) NE;TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator!=(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) NE;TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator+(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2);TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator-(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2);TE <uint Y,uint X,uint Z,TY T>MA<Y,Z,T> operator*(CO MA<Y,X,T>& mat1,CO MA<X,Z,T>& mat2);TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator*(CO MA<Y,X,T>& mat,CO T& scalar);TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator*(CO T& scalar,CO MA<Y,X,T>& mat);TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator%(CO MA<Y,X,T>& mat,CO T& scalar);TE <uint Y,uint X,TY T>MA<X,Y,T> Transpose(CO MA<Y,X,T>& mat);TE <uint X,TY T>T Trace(CO MA<X,X,T>& mat);TE <uint Y,uint X,TY T> IN MA<Y,X,T>::MA(CO T& t) NE:m_M() { operator=(move(Scalar(t))); }TE <uint Y,uint X,TY T> IN MA<Y,X,T>::MA(CO int& t) NE:MA(T(1)) {}TE <uint Y,uint X,TY T> TE <TY... Args>MA<Y,X,T>::MA(CO Args&... args) NE: m_M(){VE<T> vec{};COructTable(m_M,vec,args...);}TE <uint Y,uint X,TY T> IN MA<Y,X,T>::MA(CO MA<Y,X,T>& mat) NE:m_M(mat.m_M) {}TE <uint Y,uint X,TY T> IN MA<Y,X,T>::MA(MA<Y,X,T>&& mat) NE:m_M(move(mat.m_M)) {}TE <uint Y,uint X,TY T> TE <TY... Args> IN MA<Y,X,T>::MA(CO TableTypeForMA<T>& M) NE:m_M(M) {}TE <uint Y,uint X,TY T> TE <TY... Args> IN MA<Y,X,T>::MA(TableTypeForMA<T>&& M) NE:m_M(move(M)) {}TE <uint Y,uint X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::operator=(CO MA<Y,X,T>& mat) NE { m_M = mat.m_M; RE *this; }TE <uint Y,uint X,TY T>MA<Y,X,T>& MA<Y,X,T>::operator+=(CO MA<Y,X,T>& mat){auto I1y = m_M.begin(),end1y = m_M.end();auto I2y = mat.m_M.begin(); while(I1y != end1y){auto I1xy = I1y->begin(),end1xy = I1y->end();auto I2xy = I2y->begin(); while(I1xy != end1xy){*I1xy += *I2xy;I1xy++;I2xy++;}I1y++;I2y++;}RE *this;}TE <uint Y,uint X,TY T>MA<Y,X,T>& MA<Y,X,T>::operator-=(CO MA<Y,X,T>& mat){auto I1y = m_M.begin(),end1y = m_M.end();auto I2y = mat.m_M.begin(); while(I1y != end1y){auto I1xy = I1y->begin(),end1xy = I1y->end();auto I2xy = I2y->begin(); while(I1xy != end1xy){*I1xy -= *I2xy;I1xy++;I2xy++;}I1y++;I2y++;}RE *this;}TE <uint Y,uint X,TY T> MA<Y,X,T>& MA<Y,X,T>::operator*=(CO T& scalar) NE{for(auto Iy = m_M.begin(),endy = m_M.end();Iy != endy;Iy++){for(auto Ixy = Iy->begin(),endxy = Iy->end();Ixy != endxy;Ixy++){*Ixy *= scalar;}}RE *this;}TE <uint Y,uint X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::operator*=(CO MA<X,X,T>& mat) NE { RE operator=(move(*this * mat)); }TE <uint Y,uint X,TY T> MA<Y,X,T>& MA<Y,X,T>::operator%=(CO T& scalar) NE{for(auto Iy = m_M.begin(),endy = m_M.end();Iy != endy;Iy++){for(auto Ixy = Iy->begin(),endxy = Iy->end();Ixy != endxy;Ixy++){*Ixy %= scalar;}}RE *this;}TE <uint Y,uint X,TY T> IN TableTypeForMA<T>& MA<Y,X,T>::RefTable() NE { RE m_M; }TE <uint Y,uint X,TY T> IN CO TableTypeForMA<T>& MA<Y,X,T>::GetTable() CO NE { RE m_M; }TE <uint Y,uint X,TY T> IN CO MA<Y,X,T>& MA<Y,X,T>::Zero() NE { ST CO MA<Y,X,T> zero = move(Zero_Body()); RE zero; }TE <uint Y,uint X,TY T> IN CO MA<Y,X,T>& MA<Y,X,T>::Unit() NE { ST CO MA<Y,X,T> unit = move(Scalar(T(1))); RE unit; }TE <uint Y,uint X,TY T>MA<Y,X,T> MA<Y,X,T>::Zero_Body() NE{VE<T> vec(X);TableTypeForMA<T> M(Y,vec);RE MA<Y,X,T>(move(M));}TE <uint Y,uint X,TY T>MA<Y,X,T> MA<Y,X,T>::Scalar(CO T& t) NE{MA<Y,X,T> M{ move(Zero_Body()) };CE CO uint minXY = Y < X ? Y:X;for(uint y = 0;y < minXY;y++){M.m_M[y][y] = t;}RE M;}TE <uint Y,uint X,TY T> IN void MA<Y,X,T>::COructTable(TableTypeForMA<T>& M,VE<T>& vec) NE { M.push_back(move(vec)); }TE <uint Y,uint X,TY T> TE <TY... Args> void MA<Y,X,T>::COructTable(TableTypeForMA<T>& M,VE<T>& vec,CO T& t,CO Args&... args) NE{vec.push_back(t);if(vec.size() == X){VE<T> v{};v.swap(vec);COructTable(M,v);}if(M.size() < Y){COructTable(M,vec,args...);}RE;}TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator==(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) NE { RE mat1.GetTable() == mat2.GetTable(); }TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator!=(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) NE { RE !(mat1 == mat2); }TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator+(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) { RE MA<Y,X,T>(mat1) += mat2; }TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator-(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) { RE MA<Y,X,T>(mat1) -= mat2; }TE <uint Y,uint X,uint Z,TY T> IN MA<Y,Z,T> operator*(CO MA<Y,X,T>& mat1,CO MA<X,Z,T>& mat2){CO TableTypeForMA<T>& M1 = mat1.GetTable();CO TableTypeForMA<T>& M2 = mat2.GetTable();TableTypeForMA<T> M_prod{};auto begin2x = M2.begin();for(auto I1y = M1.begin(),end1y = M1.end();I1y != end1y;I1y++){VE<T> vec{};auto begin1yx = I1y->begin(),end1yx = I1y->end();for(uint z = 0;z < Z;z++){auto I1yx = begin1yx;auto I2x = begin2x;T inner_product{};while(I1yx != end1yx){inner_product += (*I1yx) * (*I2x)[z];I1yx++;I2x++;}vec.push_back(inner_product);}M_prod.push_back(move(vec));}RE MA<Y,Z,T>(move(M_prod));}TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator*(CO MA<Y,X,T>& mat,CO T& scalar) { RE MA<Y,X,T>(mat) *= scalar; }TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator*(CO T& scalar,CO MA<Y,X,T>& mat) { RE mat * scalar; }TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator%(CO MA<Y,X,T>& mat,CO T& scalar) { RE MA<Y,X,T>(mat) %= scalar; }TE <uint Y,uint X,TY T>MA<X,Y,T> Transpose(CO MA<Y,X,T>& mat){CO TableTypeForMA<T>& M = mat.GetTable();TableTypeForMA<T> M_t{};auto beginy = M.begin();for(auto I1x = beginy->begin(),end1x = beginy->end();I1x != end1x;I1x++){M_t.push_back(VE<T>());}for(auto Iy = beginy,endy = M.end();Iy != endy;Iy++){auto Iyx = Iy->begin(),endyx = Iy->end();auto I_ty = M_t.begin();while(Iyx != endyx){I_ty->push_back(*Iyx);Iyx++;I_ty++;}}RE MA<X,Y,T>(M_t);}TE <uint X,TY T>T Trace(CO MA<X,X,T>& mat){int i = 0;T answer =0;CO TableTypeForMA<T>& M = mat.GetTable();for(auto Iy = M.begin(),endy = M.end();Iy != endy;Iy++){answer += (*Iy)[i];i++;}RE answer;}TE <TY T>void SetIntervalEvaluation(CO uint& deg,CO T& t_start,CO uint& length,VE<T>& eval){for(uint d = 0;d <= deg;d++){eval[d] *= PO<T>::factorial_inverse(d);}VE<T> v{};v.swap(eval);TRPO<T> f{ deg + 1,move(v) };ST PO<T> exp_inv{};for(uint d = exp_inv.size();d <= deg;d++){exp_inv[d] = (d % 2 == 0 ? PO<T>::factorial_inverse(d):- PO<T>::factorial_inverse(d));}f *= exp_inv;f.RemoveRedundantZero();uint deg_f = f.size();if(deg_f == 0){eval = move(VE<T>(length,PO<T>::CO_zero()));RE;}f.SetTruncation(deg_f);deg_f--;for(uint d = 0;d <= deg_f;d++){f[d] *= PO<T>::factorial(d);}uint deg_f_half = (deg_f + 1) / 2;for(uint d = 0;d < deg_f_half;d++){swap(f[d],f[deg_f - d]);}PO<T> exp_t_Mahler{};T t_Mahler = PO<T>::CO_one();for(uint d = 0;d <= deg_f;d++){exp_t_Mahler[d] = PO<T>::factorial_inverse(d) * t_Mahler;t_Mahler *= t_start - d;}f *= exp_t_Mahler;for(uint d = 0;d < deg_f_half;d++){swap(f[d],f[deg_f - d]);}for(uint d = 0;d <= deg_f;d++){f[d] *= PO<T>::factorial_inverse(d);}f.SetTruncation(length);ST PO<T> exp{};for(uint d = exp.size();d < length;d++){exp[d] = PO<T>::factorial_inverse(d);}f *= exp;for(uint d = 0;d < length;d++){f[d] *= PO<T>::factorial(d);}f.swap(eval);RE;}TE <uint Y,uint X,TY T>void SetIntervalEvaluation(CO uint& deg,CO T& t_start,CO uint& length,CO VE<MA<Y,X,T> >& sample,VE<MA<Y,X,T> >& eval){eval = move(VE<MA<Y,X,T> >(length,MA<Y,X,T>::Zero()));VE<T> sample_copy[Y][X] = {};for(uint t = 0;t <= deg;t++){CO VE<VE<T> >& table = sample[t].GetTable();for(uint y = 0;y < Y;y++){VE<T> (&sample_copy_y)[X] = sample_copy[y];CO VE<T>& table_y = table[y];for(uint x = 0;x < X;x++){sample_copy_y[x].push_back(table_y[x]);}}}for(uint y = 0;y < Y;y++){VE<T> (&sample_copy_y)[X] = sample_copy[y];for(uint x = 0;x < X;x++){VE<T>& sample_copy_yx = sample_copy_y[x];SetIntervalEvaluation(deg,t_start,length,sample_copy_yx);for(uint i = 0;i < length;i++){VE<VE<T> >& table = eval[i].RefTable();table[y][x] = sample_copy_yx[i];}}}RE;}TE <uint Y,TY T>void SetPRecursiveMAAction(CO MA<Y,Y,PO<T> >& M,MA<Y,1,T>& v,CO uint& length){if(length == 0){RE;}CO VE<VE<PO<T> > >& M_ref = M.GetTable();uint deg = 1;for(uint y = 0;y < Y;y++){CO VE<PO<T>>& M_ref_y = M_ref[y];for(uint x = 0;x < Y;x++){CO uint size = M_ref_y[x].size();if(deg < size){deg = size;} }}deg--;uint interval_length = 1;int exponent = 0;while(interval_length * (interval_length * deg + 1) < length){interval_length *= 2;exponent++;}interval_length /= 2;exponent--;uint interval_num_max;uint t_rest_start;VE<T> point{};if(interval_length > 0){interval_num_max = length / interval_length - 1;t_rest_start = interval_length * (interval_num_max + 1);uint subinterval_num_max = deg;T subinterval_length = PO<T>::CO_one();SET_MATRIX_MULTIPOINT_EVALUATION(subinterval_num_max,t * interval_length);for(int e = 1;e < exponent;e++){MULTIPLY_SUBPRODUCT_OF_PRECURSIVE_MATRIX(subinterval_num_max);subinterval_num_max *= 2;subinterval_length *= 2;}uint rest_interval_length = interval_num_max - subinterval_num_max;MULTIPLY_SUBPRODUCT_OF_PRECURSIVE_MATRIX(rest_interval_length);for(uint t = 0;t <= interval_num_max;t++){v = move(sample[t] * v);}} else {interval_num_max = t_rest_start = 0;}if(t_rest_start < length){uint rest_num_max = length - t_rest_start - 1;SET_MATRIX_MULTIPOINT_EVALUATION(rest_num_max,t + t_rest_start);for(uint t = 0;t <= rest_num_max;t++){v = move(sample[t] * v);}}RE;}class Query{PU:ll m_N;ll m_K;int m_t;IN Query(CO ll& N = 0,CO ll& K = 0,int t = 0):m_N(N),m_K(K),m_t(t) {}};IN bool operator<(CO Query& q1,CO Query& q2) { RE q1.m_K > q2.m_K; }int main(){UNTIE;CEXPR(int,bound_T,100000);CIN_ASSERT(T,1,bound_T);CEXPR(ll,bound_N,1000000000000000000);CEXPR(ll,bound_K1,bound_T);CEXPR(ll,bound_K2,bound_N);using MOD = Mod<P>;using MODX = PO<MOD>;CO MOD& CO_zero = MODX::CO_zero();CO MOD& CO_one = MODX::CO_one();MOD CO_two{ 2 };MOD CO_two_inv{ (P + 1) / 2 };CO MODX& zero = MODX::zero();MODX one{ 0,CO_one };MODX X{ 1,CO_one };MODX X2_minus_half{ 2,- CO_two_inv };MA<2,1,MOD> v{CO_one,CO_zero};if(T > 5){ST Query Q[bound_T];FOR(t,0,T){CIN_ASSERT(Nt,1,bound_N);CIN_ASSERT(Kt,0,min(Nt * 2,bound_K1));Q[t] = Query(Nt,Kt,t);}sort(Q,Q + T);ll K_lim = Q[0].m_K;LI<LI<MA<2,2,MODX> > > MXk_prod{};MXk_prod.push_front(LI<MA<2,2,MODX> >());LI<MA<2,2,MODX> >& MXk_prod_init = MXk_prod.front();LI<MOD> point{};LI<MA<2,2,MODX> > MXk{};FOR(t,0,T){Query& Qt = Q[t];PROD_MXK(Qt.m_K);MXk_prod_init.push_back(move(Prod(MXk)));point.push_back(Qt.m_N);K_lim = Qt.m_K;MXk.clear();}SetProductTree(MXk_prod);LI<LI<MODX> > pt{};SetPointTree(point,pt);auto I_pt = pt.begin();LI<MA<2,2,MODX> > residue{};PROD_MXK(0);residue.push_front(move(Prod(MXk) %= I_pt->front()));I_pt++;auto I_MXk_prod = MXk_prod.begin(),end_MXk_prod = MXk_prod.end();I_MXk_prod++;while(I_MXk_prod != end_MXk_prod){auto I_MXk_prod_node = I_MXk_prod->begin(),end_MXk_prod_node = I_MXk_prod->end();auto I_pt_node = I_pt->begin();FOR_I(residue,I_residue,end_residue){I_MXk_prod_node++;if(I_MXk_prod_node != end_MXk_prod_node){MODX& pt_node_curr = *I_pt_node;residue.insert(I_residue,move(((*I_MXk_prod_node %= pt_node_curr) * (*I_residue % pt_node_curr)) %= pt_node_curr));I_pt_node++;*I_residue %= *I_pt_node;I_MXk_prod_node++;I_pt_node++;} else {break;}}I_MXk_prod++;I_pt++;}ST ll answer[bound_T];auto I_residue = residue.begin();FOR(t,0,T){CO VE<VE<MODX> >& residue_t = I_residue->m_M;CO VE<MODX>& residue_t_0 = residue_t[0];CO VE<MODX>& residue_t_1 = residue_t[1];MA<2,2,MOD> residue_t_val{residue_t_0[0][0],residue_t_0[1][0] ,residue_t_1[0][0],residue_t_1[1][0]};answer[Q[t].m_t] = (residue_t_val * v).m_M[0][0].Represent();I_residue++;}FOR(t,0,T){cout << answer[t] << "\n";}} else {REPEAT(T){CIN_ASSERT(N,1,bound_N);CIN_ASSERT(K,0,min(N * 2,bound_K2));if(K >= P){cout << 0 << "\n";} else {MA<2,2,MODX> MNX{X * (-CO_two) + CO_two * N,X2_minus_half + X * (CO_two_inv + N) ,one,zero};MA<2,1,MOD> v_copy{ v };SetPRecursiveMAAction(MNX,v_copy,K);cout << v_copy.m_M[0][0] << "\n";}}}QUIT;}
yukicoder

結果

テストケース

ソースコード
