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

提出ソース
結果

問題	No.2166 Paint and Fill
ユーザー	👑 p-adic
提出日時	2022-12-24 22:38:06
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	65,113 bytes
コンパイル時間	7,715 ms
コンパイル使用メモリ	319,004 KB
実行使用メモリ	428,452 KB
最終ジャッジ日時	2024-04-29 05:04:08
合計ジャッジ時間	75,370 ms
ジャッジサーバーID （参考情報）	judge2 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 6,016 KB
testcase_01	AC	2,014 ms 45,632 KB
testcase_02	AC	2,128 ms 203,496 KB
testcase_03	AC	97 ms 12,288 KB
testcase_04	AC	98 ms 12,272 KB
testcase_05	AC	94 ms 12,288 KB
testcase_06	AC	98 ms 12,280 KB
testcase_07	AC	93 ms 12,160 KB
testcase_08	AC	9,832 ms 285,752 KB
testcase_09	AC	9,936 ms 285,832 KB
testcase_10	AC	9,919 ms 285,960 KB
testcase_11	AC	9,949 ms 285,624 KB
testcase_12	AC	9,938 ms 285,736 KB
testcase_13	TLE	-
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 TE template
#define TY typename
#define ST static
#define IN inline
#define PU public
#define PR PU
#define OP operator
#define CE constexpr
#define CO const
#define RE return 
#define NE noexcept
#define WH while
#define VE vector
#define LI list
#define SZ size
#define MO move
#define C_INT CO int
#define C_UINT CO uint&
#define CR_UINT CO uint&
#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 ) constexpr const 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_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) 
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) 
#define QUIT return 0 
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"; 
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT 
TE <TY T> IN T Residue(CO T& a,CO T& p){ RE a >= 0 ? a % p:p - (- a - 1) % p - 1; }TE <ll M>class Mod{PR: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;WH(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;WH(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 SZ = p_inverse->SZ();for(ll i = SZ;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(); }
#define RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(CONDITION) if(CONDITION){ RE OP=(zero); } 
#define RE_ZERO_FOR_TR_MU_CO_FOR_TR_POLYNOMIAL_IF(CONDITION) if(CONDITION){ RE TRPO<T>(m_N); } 
#define SET_VE_FOR_AN_OF_MU_FOR_TR_POLYNOMIAL(N_OUTPUT_LIM) if(PO<T>::m_SZ < N_OUTPUT_LIM){ for(uint i = PO<T>::m_SZ;i < N_OUTPUT_LIM;i++){ PO<T>::m_f.push_back(0); } PO<T>::m_SZ = N_OUTPUT_LIM; } 
#define SET_VE_FOR_AN_OF_TR_MU_CO_FOR_TR_POLYNOMIAL(N_OUTPUT_LIM) VE<T> AN(N_OUTPUT_LIM) 
#define SET_SUM_OF_MU_FOR_TR_POLYNOMIAL PO<T>::m_f[i] = sum 
#define SET_SUM_OF_TR_MU_CO_FOR_TR_POLYNOMIAL AN[i] = sum 
#define SET_N_INPUT_START_FOR_MU_FOR_TR_POLYNOMIAL(F,SZ,N_INPUT_START_NUM) uint N_INPUT_START_NUM; for(uint i = 0;i < SZ && searching;i++){ if(F[i] != zero){ N_INPUT_START_NUM = i; searching = false; } } 
#define SET_N_INPUT_MAX_FOR_MU_FOR_TR_POLYNOMIAL(F,SZ,N_INPUT_MAX_NUM) uint N_INPUT_MAX_NUM; searching = true; for(uint i = (SZ) - 1;searching;i--){ if(F[i] != zero){ N_INPUT_MAX_NUM = i; searching = false; } } 
#define CONVOLUTION_FOR_MU_FOR_TR_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_TR_MU_CO_FOR_TR_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 = AN[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 ZEROIFICATION_FOR_MU_FOR_TR_POLYNOMIAL for(uint i = 0;i < N_input_start_0_start_1;i++){ PO<T>::m_f[i] = 0; } 
#define ZEROIFICATION_FOR_TR_MU_CO_FOR_TR_POLYNOMIAL for(uint i = 0;i < N_input_start_0_start_1;i++){ AN[i] = 0; } 
#define CN(S1,S2) SUBSTITUTE_CN(S1,S2) 
#define SUBSTITUTE_CN(S1,S2) S1 ## S2 
#define DF_0_OF__FOR_TR_POLYNOMIAL(MU,ACCESS_ENTRY) CN(CN(RE_ZERO_FOR_,MU),_FOR_TR_POLYNOMIAL_IF)(PO<T>::m_SZ == 0); uint N_output_max = PO<T>::m_SZ + f.PO<T>::m_SZ - 2; if(N_output_max >= m_N){ N_output_max = m_N - 1; } CO uint N_output_lim = N_output_max + 1; CN(CN(SET_VE_FOR_AN_OF_,MU),_FOR_TR_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); } CN(CN(SET_SUM_OF_,MU),_FOR_TR_POLYNOMIAL); searching = i > 0; } 
#define DF_0_OF_MU_FOR_TR_POLYNOMIAL DF_0_OF__FOR_TR_POLYNOMIAL(MU,PO<T>::m_f[j]) 
#define DF_0_OF_TR_MU_CO_FOR_TR_POLYNOMIAL DF_0_OF__FOR_TR_POLYNOMIAL(TR_MU_CO,PO<T>::OP[](j)) 
#define DF_1_OF__FOR_TR_POLYNOMIAL(MU) SET_N_INPUT_START_FOR_MU_FOR_TR_POLYNOMIAL(PO<T>::m_f,PO<T>::m_SZ,N_input_start_0); CN(CN(RE_ZERO_FOR_,MU),_FOR_TR_POLYNOMIAL_IF)(searching); searching = true; SET_N_INPUT_START_FOR_MU_FOR_TR_POLYNOMIAL(f,f.PO<T>::m_SZ,N_input_start_1); 
#define DF_1_OF_MU_FOR_TR_POLYNOMIAL DF_1_OF__FOR_TR_POLYNOMIAL(MU) 
#define DF_1_OF_TR_MU_CO_FOR_TR_POLYNOMIAL DF_1_OF__FOR_TR_POLYNOMIAL(TR_MU_CO) 
#define DF_2_OF_MU_FOR_TR_POLYNOMIAL SET_N_INPUT_MAX_FOR_MU_FOR_TR_POLYNOMIAL(PO<T>::m_f,PO<T>::m_SZ,N_input_max_0); SET_N_INPUT_MAX_FOR_MU_FOR_TR_POLYNOMIAL(f,f.PO<T>::m_SZ < m_N ? f.PO<T>::m_SZ: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 DF_2_OF_TR_MU_CO_FOR_TR_POLYNOMIAL DF_2_OF_MU_FOR_TR_POLYNOMIAL 
#define DF_3_OF__FOR_TR_POLYNOMIAL(MU) 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; CN(CN(SET_VE_FOR_AN_OF_,MU),_FOR_TR_POLYNOMIAL)(N_output_lim_fixed); for(uint i = N_output_max_fixed;i > N_input_start_0_max_1;i--){ CN(CN(CONVOLUTION_FOR_,MU),_FOR_TR_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--){ CN(CN(CONVOLUTION_FOR_,MU),_FOR_TR_POLYNOMIAL)(N_input_start_0); searching = i > N_input_start_0_start_1; } CN(CN(ZEROIFICATION_FOR_,MU),_FOR_TR_POLYNOMIAL); 
#define DF_3_OF_MU_FOR_TR_POLYNOMIAL DF_3_OF__FOR_TR_POLYNOMIAL(MU) 
#define DF_3_OF_TR_MU_CO_FOR_TR_POLYNOMIAL DF_3_OF__FOR_TR_POLYNOMIAL(TR_MU_CO) 
#define DF_4_OF_MU_FOR_TR_POLYNOMIAL 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> }; WH(N_input_truncated_deg_0_deg_1 >= two_power){ two_power *= 2; two_power_inv /= 2; exponent++; } VE<T> f0{ FFT<T>(PO<T>::m_f,N_input_start_0,N_input_max_0 + 1,0,two_power,exponent) }; CO VE<T> f1{ 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 DF_4_OF_TR_MU_CO_FOR_TR_POLYNOMIAL DF_4_OF_MU_FOR_TR_POLYNOMIAL 
#define DF_OF_INVERSE_FOR_TR_POLYNOMIAL(TYPE,RECURSION) CR_UINT N = f.GetTruncation(); uint power; uint power_2 = 1; TRPO< TYPE > f_inv{ power_2,PO< TYPE >::CO_one() / f[0] }; WH(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_POLYNOMIAL(TYPE,RECURSION) CR_UINT N = f.GetTruncation(); uint power; uint power_2 = 1; TRPO< TYPE > f_exp{ power_2,PO< TYPE >::CO_one() }; WH(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_POLYNOMIAL(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_POLYNOMIAL(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_POLYNOMIAL(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_POLYNOMIAL(TYPE) TE <> PO<TYPE>& PO<TYPE>::OP*=(CO PO<TYPE>& f) { if(m_SZ != 0){ VE<TYPE> v{}; v.swap(m_f); TRPO<TYPE> f_copy{ m_SZ + f.m_SZ - 1,MO(v) }; f_copy *= f; m_f = MO(f_copy.PO<TYPE>::m_f); m_SZ = m_f.SZ(); } RE *this; }
IN CEXPR(ll,P,998244353);TE <TY T> class TRPO;TE <TY T>class PO{friend class TRPO<T>;PR:VE<T> m_f;uint m_SZ;PU:IN PO();IN PO(CO T& t);IN PO(CO PO<T>& f);IN PO(PO<T>&& f);IN PO(C_UINT i,CO T& t);IN PO(VE<T>&& f);PO<T>& OP=(CO T& t);PO<T>& OP=(CO PO<T>& f);PO<T>& OP=(PO<T>&& f);IN CO T& OP[](C_UINT i) CO;IN T& OP[](C_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 CR_UINT SZ() CO NE;IN void swap(PO<T>& f);IN void swap(VE<T>& f);void ReMORedundantZero();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(C_UINT i);ST IN CO T& factorial_inverse(C_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,C_UINT N_output_start_plus_one);TE <TY T> TRPO<T> TRIntegral(CO TRPO<T>& f,C_UINT N_output_start);TE <TY T> class TRPO;TE <TY T> TRPO<T> TRDifferential(CO TRPO<T>& f,C_UINT N_output_start_plus_one);TE <TY T> TRPO<T> TRIntegral(CO TRPO<T>& f,C_UINT N_output_start);TE <TY T>class TRPO :PU PO<T>{friend TRPO<T> TRDifferential<T>(CO TRPO<T>& f,C_UINT N_output_start_plus_one);friend TRPO<T> TRIntegral<T>(CO TRPO<T>& f,C_UINT N_output_start);PR:uint m_N;PU:IN TRPO(C_UINT N = 0);IN TRPO(CO TRPO<T>& f);IN TRPO(TRPO<T>&& f);IN TRPO(C_UINT N,CO T& t);TRPO(C_UINT N,CO PO<T>& f);IN TRPO(C_UINT N,PO<T>&& f);IN TRPO(C_UINT N,C_UINT i,CO T& t);IN TRPO(C_UINT N,VE<T>&& f);IN TRPO<T>& OP=(CO TRPO<T>& f);IN TRPO<T>& OP=(TRPO<T>&& f);IN TRPO<T>& OP=(CO T& t);IN TRPO<T>& OP=(CO PO<T>& f);IN TRPO<T>& OP=(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,C_UINT N_input_start,C_UINT N_input_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,C_UINT N_input_start,C_UINT N_input_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,C_UINT N_input_start,C_UINT N_input_lim);TRPO<T>& FFT_TRMU(CO PO<T>& f,C_UINT N_input_start,C_UINT N_input_lim);TRPO<T> TRMU_CO(CO PO<T>& f,C_UINT N_output_start,C_UINT N_output_lim) CO;TRPO<T> FFT_TRMU_CO(CO PO<T>& f,C_UINT N_output_start,C_UINT 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(C_UINT N) NE;IN CR_UINT GetTruncation() CO NE;IN TRPO<T>& TruncateInitial(C_UINT N) NE;IN TRPO<T>& TruncateFinal(C_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(C_UINT i,CO TRPO<T>& f);TE <TY T> TRPO<T> TRDifferential(CO TRPO<T>& f,C_UINT 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,C_UINT 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 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,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT two_power,C_UINT exponent);TE <TY T> IN VE<T> FFT(CO VE<T>& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT N_output_start,C_UINT N_output_lim,C_UINT N_output_shift,C_UINT two_power,C_UINT exponent);TE <TY T> VE<T> IFFT(CO VE<T>& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT two_power,CO T& two_power_inv,C_UINT exponent);TE <TY T> VE<T> IFFT(CO VE<T>& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT N_output_start,C_UINT N_output_lim,C_UINT N_output_shift,C_UINT two_power,CO T& two_power_inv,C_UINT exponent);TE <> IN CE CO uint LimitOfPowerForFFT<Mod<998244353> > = 24;TE <> IN CE CO uint BorderForFFT<Mod<998244353> > = 4; TE <> IN CO Mod<998244353> (&PrimitiveRootOfTwoForFFT() NE)[LimitOfPowerForFFT<Mod<998244353> >]{ST CO Mod<998244353> PRT[ LimitOfPowerForFFT<Mod<998244353> > ] ={Mod<998244353>(1) ,Mod<998244353>(998244352) ,Mod<998244353>(911660635) ,Mod<998244353>(625715529) ,Mod<998244353>(373294451) ,Mod<998244353>(827987769) ,Mod<998244353>(280333251) ,Mod<998244353>(581015842) ,Mod<998244353>(628092333) ,Mod<998244353>(300892551) ,Mod<998244353>(586046298) ,Mod<998244353>(615001099) ,Mod<998244353>(318017948) ,Mod<998244353>(64341522) ,Mod<998244353>(106061068) ,Mod<998244353>(304605202) ,Mod<998244353>(631920086) ,Mod<998244353>(857779016) ,Mod<998244353>(841431251) ,Mod<998244353>(805775211) ,Mod<998244353>(390359979) ,Mod<998244353>(923521) ,Mod<998244353>(961) ,Mod<998244353>(31)};RE PRT;}TE <> IN CO Mod<998244353> (&InversePrimitiveRootOfTwoForFFT() NE)[LimitOfPowerForFFT<Mod<998244353> >]{ST CO Mod<998244353> PRT[ LimitOfPowerForFFT<Mod<998244353> > ] ={Mod<998244353>(1) ,Mod<998244353>(998244352) ,Mod<998244353>(86583718) ,Mod<998244353>(488723995) ,Mod<998244353>(369330050) ,Mod<998244353>(543653592) ,Mod<998244353>(382946991) ,Mod<998244353>(844956623) ,Mod<998244353>(91420391) ,Mod<998244353>(433414612) ,Mod<998244353>(288894979) ,Mod<998244353>(260490556) ,Mod<998244353>(857007890) ,Mod<998244353>(736054570) ,Mod<998244353>(474649464) ,Mod<998244353>(948509906) ,Mod<998244353>(114942468) ,Mod<998244353>(962405921) ,Mod<998244353>(667573957) ,Mod<998244353>(46809892) ,Mod<998244353>(304321983) ,Mod<998244353>(30429817) ,Mod<998244353>(293967900) ,Mod<998244353>(128805723)};RE PRT;}TE <TY T>ST VE<T> FFT_Body(CO VE<T>& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT N_output_start,C_UINT N_output_lim,C_UINT N_output_shift,C_UINT two_power,C_UINT exponent,CO T (&PRT)[LimitOfPowerForFFT<T>]);TE <TY T>ST VE<T> FFT_Body(CO VE<T>& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT two_power,C_UINT exponent,C_UINT start,C_UINT depth,CO T (&PRT)[LimitOfPowerForFFT<T>]);TE <TY T> IN VE<T> FFT(CO VE<T>& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT two_power,C_UINT 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,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT N_output_start,C_UINT N_output_lim,C_UINT N_output_shift,C_UINT two_power,C_UINT 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,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT two_power,CO T& two_power_inv,C_UINT exponent){VE<T> AN{ FFT_Body<T>(f,N_input_start,N_input_lim,N_input_shift,two_power,exponent,InversePrimitiveRootOfTwoForFFT<T>()) };CO uint SZ = AN.SZ();for(uint i = 0;i < SZ;i++){AN[i] *= two_power_inv;}RE AN;}TE <TY T>VE<T> IFFT(CO VE<T>& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT N_output_start,C_UINT N_output_lim,C_UINT N_output_shift,C_UINT two_power,CO T& two_power_inv,C_UINT exponent){VE<T> AN{ 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 SZ = AN.SZ();CO uint N_output_length = N_output_lim - N_output_start + N_output_shift;if(SZ < N_output_length){SZ = N_output_length;}for(uint i = N_output_shift;i < SZ;i++){AN[i] *= two_power_inv;}RE AN;}TE <TY T>ST VE<T> FFT_Body(CO VE<T>& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT N_output_start,C_UINT N_output_lim,C_UINT N_output_shift,C_UINT two_power,C_UINT exponent,CO T (&PRT)[LimitOfPowerForFFT<T>]){CO uint length = N_output_lim - N_output_start + N_output_shift;VE<T> AN(length);if(two_power == 1){if(N_input_shift == 0 && N_output_shift < length){if(N_input_start < N_input_lim){AN[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++;}WH(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> AN_sub0{ FFT_Body<T>(f,N_input_start,N_input_lim,N_input_shift,two_power_sub,exponent_sub,0,2,PRT) };VE<T> AN_sub1{ 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;AN[i - N_output_start + N_output_shift] = AN_sub0[i_sub] + zeta_power * AN_sub1[i_sub];zeta_power *= zeta;}}RE AN;}TE <TY T>ST VE<T> FFT_Body(CO VE<T>& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT two_power,C_UINT exponent,C_UINT start,C_UINT depth,CO T (&PRT)[LimitOfPowerForFFT<T>]){VE<T> AN(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 };WH(j_hit != 0){if(j_hit % 2 == 1){zeta_power *= zeta_power_2;}zeta_power_2 *= zeta_power_2;j_hit /= 2;}AN[0] = f[index_hit];for(uint i = 1;i < two_power;i++){AN[i] = zeta_power * AN[i-1];}} else if(count > 1){CO T& zeta = PRT[exponent];CO T& one = PRT[0];T zeta_power{ one };CE C_UINT border = BorderForFFT<T>;if(exponent < border){for(uint i = 0;i < two_power;i++){T& AN_i = AN[i];T zeta_power_power{ one };T zeta_power_power_2{ zeta_power };uint j_min_copy = j_min;WH(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++){AN_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> AN_sub0{ FFT_Body<T>(f,N_input_start,N_input_lim,N_input_shift,two_power_sub,exponent_sub,start,depth_sub,PRT) };VE<T> AN_sub1{ 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;AN[i] = AN_sub0[i_sub] + zeta_power * AN_sub1[i_sub];zeta_power *= zeta;}}}}RE AN;}TE <TY T> IN TRPO<T>::TRPO(C_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(TRPO<T>&& f):PO<T>(MO(f)),m_N(MO(f.m_N)) {}TE <TY T> IN TRPO<T>::TRPO(C_UINT N,CO T& t):PO<T>(t),m_N(N) {}TE <TY T>TRPO<T>::TRPO(C_UINT N,CO PO<T>& f):PO<T>(),m_N(N){CR_UINT SZ = f.PO<T>::m_SZ < m_N ? f.PO<T>::m_SZ:m_N;for(uint i = 0;i < SZ;i++){PO<T>::m_f.push_back(f.PO<T>::m_f[i]);PO<T>::m_SZ++;}}TE <TY T> IN TRPO<T>::TRPO(C_UINT N,PO<T>&& f):PO<T>(MO(f)),m_N(N) {};TE <TY T> IN TRPO<T>::TRPO(C_UINT N,C_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(C_UINT N,VE<T>&& f):PO<T>(MO(f)),m_N(N){WH(PO<T>::m_SZ > m_N){PO<T>::m_f.pop_back();PO<T>::m_SZ--;}}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=(TRPO<T>&& f) { PO<T>::OP=(MO(f)); m_N = MO(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=(PO<T>&& f) { RE OP=(TRPO<T>(m_N,MO(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_SZ); }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_SZ); }TE <TY T>TRPO<T>& TRPO<T>::TRPlus(CO PO<T>& f,C_UINT N_output_start,C_UINT N_output_limit){CR_UINT SZ = N_output_limit < m_N ? N_output_limit < f.PO<T>::m_SZ ? N_output_limit:f.PO<T>::m_SZ:m_N < f.PO<T>::m_SZ ? m_N:f.PO<T>::m_SZ;CR_UINT SZ_min = PO<T>::m_SZ < SZ ? PO<T>::m_SZ:SZ;for(uint i = N_output_start;i < SZ_min;i++){PO<T>::m_f[i] += f.PO<T>::m_f[i];}for(uint i = PO<T>::m_SZ;i < SZ;i++){PO<T>::m_f.push_back(f.PO<T>::m_f[i]);PO<T>::m_SZ++;}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_SZ); }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_SZ); }TE <TY T>TRPO<T>& TRPO<T>::TRMinus(CO PO<T>& f,C_UINT N_output_start,C_UINT N_output_limit){CR_UINT SZ = N_output_limit < m_N ? N_output_limit < f.PO<T>::m_SZ ? N_output_limit:f.PO<T>::m_SZ:m_N < f.PO<T>::m_SZ ? m_N:f.PO<T>::m_SZ;CR_UINT SZ_min = PO<T>::m_SZ < SZ ? PO<T>::m_SZ:SZ;for(uint i = N_output_start;i < SZ_min;i++){PO<T>::m_f[i] -= f.PO<T>::m_f[i];}for(uint i = PO<T>::m_SZ;i < SZ;i++){PO<T>::m_f.push_back(- f.PO<T>::m_f[i]);PO<T>::m_SZ++;}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_POLYNOMIAL(Mod<998244353>,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 searching = true;if(PO<T>::m_SZ < border_0 && f.PO<T>::m_SZ < border_0){RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(f.PO<T>::m_SZ == 0);DF_0_OF_MU_FOR_TR_POLYNOMIAL;} else {DF_1_OF_MU_FOR_TR_POLYNOMIAL;RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(searching);DF_2_OF_MU_FOR_TR_POLYNOMIAL;CO uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1:m_N;RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(N_input_start_0_start_1 >= m_N);DF_3_OF_MU_FOR_TR_POLYNOMIAL;}RE *this;}TE <TY T>TRPO<T>& TRPO<T>::FFT_MU(CO PO<T>& f){CE C_UINT border_0 = FFT_MU_border_0<T>;CO T& zero = PO<T>::CO_zero();bool searching = true;if(PO<T>::m_SZ < border_0 && f.PO<T>::m_SZ < border_0){RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(f.PO<T>::m_SZ == 0);DF_0_OF_MU_FOR_TR_POLYNOMIAL;} else {DF_1_OF_MU_FOR_TR_POLYNOMIAL;RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(searching);DF_2_OF_MU_FOR_TR_POLYNOMIAL;CO uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1:m_N;RE_ZERO_FOR_MU_FOR_TR_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;CE C_UINT border_1 = FFT_MU_border_1<T>;if(N_input_truncated_deg_0_deg_1 < border_1){DF_3_OF_MU_FOR_TR_POLYNOMIAL;} else {DF_4_OF_MU_FOR_TR_POLYNOMIAL;PO<T>::m_f = IFFT<T>(f0,0,two_power,0,0,N_output_lim_fixed - N_input_start_0_start_1,N_input_start_0_start_1,two_power,two_power_inv,exponent);PO<T>::m_SZ = PO<T>::m_f.SZ();}}RE *this;}TE <TY T> TRPO<T>& TRPO<T>::TRMU(CO PO<T>& f,C_UINT N_output_start,C_UINT N_output_lim){CE CO uint border_0 = 21;CO T& zero = PO<T>::CO_zero();bool searching = true;if(PO<T>::m_SZ < border_0 && f.PO<T>::m_SZ < border_0){DF_0_OF_MU_FOR_TR_POLYNOMIAL;} else {DF_1_OF_MU_FOR_TR_POLYNOMIAL;DF_2_OF_MU_FOR_TR_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;}RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(N_input_start_0_start_1 >= N_output_lim_fixed);DF_3_OF_MU_FOR_TR_POLYNOMIAL;}RE *this;}TE <TY T> TRPO<T>& TRPO<T>::FFT_TRMU(CO PO<T>& f,C_UINT N_output_start,C_UINT N_output_lim){CE C_UINT border_0 = FFT_MU_border_0<T>;CO T& zero = PO<T>::CO_zero();bool searching = true;if(PO<T>::m_SZ < border_0 && f.PO<T>::m_SZ < border_0){DF_0_OF_MU_FOR_TR_POLYNOMIAL;} else {DF_1_OF_MU_FOR_TR_POLYNOMIAL;DF_2_OF_MU_FOR_TR_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;}RE_ZERO_FOR_MU_FOR_TR_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;CE C_UINT border_1 = FFT_MU_border_1<T>;if(N_input_truncated_deg_0_deg_1 < border_1){DF_3_OF_MU_FOR_TR_POLYNOMIAL;} else {DF_4_OF_MU_FOR_TR_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 = 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_VE_FOR_AN_OF_MU_FOR_TR_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>::TRMU_CO(CO PO<T>& f,C_UINT N_output_start,C_UINT N_output_lim) CO{CE CO uint border_0 = 21;CO T& zero = PO<T>::CO_zero();bool searching = true;if(PO<T>::m_SZ < border_0 && f.PO<T>::m_SZ < border_0){DF_0_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;RE TRPO<T>(m_N,MO(AN));}DF_1_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;DF_2_OF_TR_MU_CO_FOR_TR_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;}RE_ZERO_FOR_TR_MU_CO_FOR_TR_POLYNOMIAL_IF(N_input_start_0_start_1 >= N_output_lim_fixed);DF_3_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;RE TRPO<T>(m_N,MO(AN));}TE <TY T> TRPO<T> TRPO<T>::FFT_TRMU_CO(CO PO<T>& f,C_UINT N_output_start,C_UINT N_output_lim) CO{CE C_UINT border_0 = FFT_MU_border_0<T>;CO T& zero = PO<T>::CO_zero();bool searching = true;if(PO<T>::m_SZ < border_0 && f.PO<T>::m_SZ < border_0){DF_0_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;RE TRPO<T>(m_N,MO(AN));}DF_1_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;DF_2_OF_TR_MU_CO_FOR_TR_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;}RE_ZERO_FOR_TR_MU_CO_FOR_TR_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;CE C_UINT border_1 = FFT_MU_border_1<T>;if(N_input_truncated_deg_0_deg_1 < border_1){DF_3_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;RE TRPO<T>(m_N,MO(AN));}DF_4_OF_TR_MU_CO_FOR_TR_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,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(C_UINT N) NE { m_N = N; TruncateFinal(m_N); }TE <TY T> IN CR_UINT TRPO<T>::GetTruncation() CO NE { RE m_N; }TE <TY T> IN TRPO<T>& TRPO<T>::TruncateInitial(C_UINT N) NE { CR_UINT SZ = N < PO<T>::m_SZ ? N:PO<T>::m_SZ; for(uint i = 0;i < SZ;i++){ PO<T>::m_f[i] = 0; } RE *this; }TE <TY T> IN TRPO<T>& TRPO<T>::TruncateFinal(C_UINT N) NE { WH(PO<T>::m_SZ > N){ PO<T>::m_f.pop_back(); PO<T>::m_SZ--; } 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(C_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,C_UINT 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_SZ){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_SZ;i++){f_dif.PO<T>::m_f.push_back(i * f.PO<T>::m_f[i]);}f_dif.PO<T>::m_SZ = f.PO<T>::m_SZ - 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,C_UINT N_output_start){TRPO<T> f_int{ f.m_N + 1 };if(N_output_start <= f.PO<T>::m_SZ){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_SZ;i++){f_int.PO<T>::m_f.push_back(f.PO<T>::m_f[i - 1] / T(i));}f_int.PO<T>::m_SZ = f.PO<T>::m_SZ + 1;}RE f_int;}TE <TY T>TRPO<T> Inverse(CO TRPO<T>& f){DF_OF_INVERSE_FOR_TR_POLYNOMIAL(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_POLYNOMIAL(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_SZ(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_SZ(f.m_SZ) {}TE <TY T> IN PO<T>::PO(PO<T>&& f):m_f(MO(f.m_f)),m_SZ(MO(f.m_SZ)) {}TE <TY T> IN PO<T>::PO(C_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(MO(f)),m_SZ(m_f.SZ()) {}TE <TY T> IN PO<T>& PO<T>::OP=(CO T& t) { m_f.clear(); m_SZ = 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_SZ = f.m_SZ; RE *this; }TE <TY T> IN PO<T>& PO<T>::OP=(PO<T>&& f) { m_f = move(f.m_f); m_SZ = move(f.m_SZ); RE *this; }TE <TY T>CO T& PO<T>::OP[](C_UINT i) CO{if(m_SZ <= i){RE CO_zero();}RE m_f[i];}TE <TY T> IN T& PO<T>::OP[](C_UINT i){if(m_SZ <= i){CO T& z = CO_zero();WH(m_SZ <= i){m_f.push_back(z);m_SZ++;}}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_SZ;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_SZ;i++){OP[](i) -= f.m_f[i];}RE *this;}DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_POLYNOMIAL(Mod<998244353>);TE <TY T>PO<T>& PO<T>::OP*=(CO T& t){if(m_SZ == 0 || t == CO_one()){RE *this;}if(t == CO_zero()){RE OP=(zero());}for(uint i = 0;i < m_SZ;i++){OP[](i) *= t;}RE *this;}TE <TY T>PO<T>& PO<T>::OP*=(CO PO<T>& f){if(m_SZ == 0){RE *this;}if(f.m_SZ == 0){RE OP=(zero());}CO uint SZ = m_SZ + f.m_SZ - 1;PO<T> product{}; for(uint i = 0;i < SZ;i++){T& product_i = product[i];CO uint j_min = m_SZ <= i ? i - m_SZ + 1:0;CO uint j_lim = i < f.m_SZ ? i + 1:f.m_SZ;for(uint j = j_min;j < j_lim;j++){product_i += m_f[i - j] * f.m_f[j];}}RE OP=(MO(product));}TE <TY T>PO<T>& PO<T>::OP/=(CO T& t){if(t == CO_one()){RE *this;}for(uint i = 0;i < m_SZ;i++){OP[](i) /= t;}RE *this;}TE <TY T>PO<T>& PO<T>::OP/=(CO PO<T>& f){if(m_SZ >= f.m_SZ){assert(f.m_SZ > 0);uint SZ0 = m_SZ - f.m_SZ + 1;TRPO<T> f0_copy(SZ0);for(uint d0 = 0;d0 < SZ0;d0++){f0_copy.PO<T>::m_f.push_back(m_f[m_SZ - 1 - d0]);}f0_copy.PO<T>::m_SZ = SZ0;TRPO<T> f1_copy(SZ0);uint SZ1 = SZ0 < f.m_SZ ? SZ0:f.m_SZ;for(uint d1 = 0;d1 < SZ1;d1++){f1_copy.PO<T>::m_f.push_back(f.m_f[f.m_SZ - 1 - d1]);}f1_copy.PO<T>::m_SZ = SZ1;f0_copy /= f1_copy;for(uint d0 = 0;d0 < SZ0;d0++){m_f[d0] = f0_copy[ SZ0 - 1 - d0 ];}WH(m_SZ > SZ0){m_f.pop_back();m_SZ--;}} else {PO<T>::m_f.clear();PO<T>::m_SZ = 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_SZ;i++){OP[](i) %= t;}RE *this;}TE <TY T>PO<T>& PO<T>::OP%=(CO PO<T>& f){if(m_SZ >= f.m_SZ){OP-=((*this / f) * f);ReMORedundantZero();}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_SZ > 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 SZ = factorial.SZ();WH(SZ < m_SZ){factorial.push_back(factorial_curr *= SZ);factorial_inv.push_back(factorial_inv_curr /= SZ);SZ++;}for(uint d = 0;d < m_SZ;d++){m_f[d] *= factorial[d];}TRPO<T> f{ m_SZ * 2 };T power_t = CO_one();for(uint d = 0;d < m_SZ;d++){f[m_SZ - 1 - d] = power_t * factorial_inv[d];power_t *= t;}f *= *this;for(uint d = 0;d < m_SZ;d++){m_f[d] = f.PO<T>::m_f[d + m_SZ - 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 CR_UINT PO<T>::SZ() CO NE { RE m_SZ; }TE <TY T> IN void PO<T>::swap(PO<T>& f) { m_f.swap(f.m_f); swap(m_SZ,f.m_SZ); }TE <TY T> IN void PO<T>::swap(VE<T>& f) { m_f.swap(f); m_SZ = m_f.SZ(); }TE <TY T>void PO<T>::ReMORedundantZero(){CO T& z = CO_zero();WH(m_SZ > 0 ? m_f[m_SZ - 1] == z:false){m_f.pop_back();m_SZ--;}RE;}TE <TY T>string PO<T>::Display() CO NE{string s = "(";if(m_SZ > 0){s += to_string(m_f[0]);for(uint i = 1;i < m_SZ;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(C_UINT i) { ST VE<T> memory = { CO_one(),CO_one() }; ST T curr = CO_one(); ST uint SZ = 2; WH(SZ <= i){ memory.push_back(curr *= SZ++); } RE memory[i]; }TE <TY T> IN CO T& PO<T>::factorial_inverse(C_UINT i) { ST VE<T> memory = { CO_one(),CO_one() }; ST T curr = CO_one(); ST uint SZ = 2; WH(SZ <= i){ memory.push_back(curr /= SZ++); } RE memory[i]; }TE <TY T>bool OP==(CO PO<T>& f0,CO T& t1){C_UINT SZ = f0.SZ();CO T& zero = PO<T>::CO_zero();for(uint i = 1;i < SZ;i++){if(f0[i] != zero){RE false;}}RE f0[0] == t1;}TE <TY T>bool OP==(CO PO<T>& f0,CO PO<T>& f1){CR_UINT SZ0 = f0.SZ();CR_UINT SZ1 = f1.SZ();CR_UINT SZ = SZ0 < SZ1 ? SZ1:SZ0;for(uint i = 0;i < SZ;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.SZ() == 1){RE f.front();}auto I = f.begin(),end = f.end();WH(I != end){T& t = *I;I++;if(I != end){t = t * *I;I = f.erase(I);}}RE Prod(f);}
TE <TY T>using TT = VE<VE<T> >;TE <uint Y,uint X,TY T>class MA{PR:TT<T> m_M;PU:IN MA(CO T& t = T()) NE;IN MA(C_INT t) NE;TE <TY... Args> IN MA(CO T& t0,CO T& t1,CO Args&... args) NE;TE <TY... Args> IN MA(T&& t0,T&& t1,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 TT<T>& M) NE;TE <TY... Args> IN MA(TT<T>&& M) NE;IN MA<Y,X,T>& operator=(CO MA<Y,X,T>& mat) NE;IN MA<Y,X,T>& operator=(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 TT<T>& RefTable() NE;IN CO TT<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(TT<T>& M,VE<T>& vec) NE;TE <TY... Args> ST void COructTable(TT<T>& M,VE<T>& vec,CO T& t,CO Args&... args) NE;TE <TY... Args> ST void COructTable(TT<T>& M,VE<T>& vec,T&& t,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=(Scalar(t)); }TE <uint Y,uint X,TY T> IN MA<Y,X,T>::MA(C_INT t) NE:MA(T(t)) {}TE <uint Y,uint X,TY T> TE <TY... Args>MA<Y,X,T>::MA(CO T& t0,CO T& t1,CO Args&... args) NE: m_M(){VE<T> vec{};COructTable(m_M,vec,t0,t1,args...);}TE <uint Y,uint X,TY T> TE <TY... Args>MA<Y,X,T>::MA(T&& t0,T&& t1,Args&&... args) NE: m_M(){VE<T> vec{};COructTable(m_M,vec,MO(t0),MO(t1),MO(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(MO(mat.m_M)) {}TE <uint Y,uint X,TY T> TE <TY... Args> IN MA<Y,X,T>::MA(CO TT<T>& M) NE:m_M(M) {}TE <uint Y,uint X,TY T> TE <TY... Args> IN MA<Y,X,T>::MA(TT<T>&& M) NE:m_M(MO(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> IN MA<Y,X,T>& MA<Y,X,T>::operator=(MA<Y,X,T>&& mat) NE { m_M = move(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(); WH(I1y != end1y){auto I1xy = I1y->begin(),end1xy = I1y->end();auto I2xy = I2y->begin(); WH(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(); WH(I1y != end1y){auto I1xy = I1y->begin(),end1xy = I1y->end();auto I2xy = I2y->begin(); WH(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=(MO(*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 TT<T>& MA<Y,X,T>::RefTable() NE { RE m_M; }TE <uint Y,uint X,TY T> IN CO TT<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 = MO(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 = MO(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);TT<T> M(Y,vec);RE MA<Y,X,T>(MO(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{ MO(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(TT<T>& M,VE<T>& vec) NE { M.push_back(MO(vec)); }TE <uint Y,uint X,TY T> TE <TY... Args> void MA<Y,X,T>::COructTable(TT<T>& M,VE<T>& vec,CO T& t,CO Args&... args) NE{vec.push_back(t);if(vec.SZ() == X){VE<T> v{};v.swap(vec);COructTable(M,v);}if(M.SZ() < Y){COructTable(M,vec,args...);}RE;}TE <uint Y , uint X , TY T> TE <TY... Args> void MA<Y,X,T>::COructTable(TT<T>& M,VE<T>& vec,T&& t,Args&&... args) NE{vec.push_back(MO(t));if(vec.SZ() == X){VE<T> v{};v.swap(vec);COructTable(M,v);}if(M.SZ() < Y){COructTable(M,vec,MO(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 TT<T>& M1 = mat1.GetTable();CO TT<T>& M2 = mat2.GetTable();TT<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{};WH(I1yx != end1yx){inner_product += (*I1yx) * (*I2x)[z];I1yx++;I2x++;}vec.push_back(inner_product);}M_prod.push_back(MO(vec));}RE MA<Y,Z,T>(MO(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 TT<T>& M = mat.GetTable();TT<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();WH(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 AN =0;CO TT<T>& M = mat.GetTable();for(auto Iy = M.begin(),endy = M.end();Iy != endy;Iy++){AN += (*Iy)[i];i++;}RE AN;}
TE <TY T,TY V>void SetMultipointEvaluation(CO PO<T>& f,CO LI<LI<PO<T> > >& point_tree,V& AN);TE <TY T,TY V> IN void SetMultipointEvaluation(CO PO<T>& f,CO V& point,V& AN) { LI<LI<PO<T> > > pt{}; SetPointTree(point,pt); SetMultipointEvaluation(f,pt,AN); }TE <TY T,TY V>void SetMultipointEvaluation(CO PO<T>& f,CO LI<LI<PO<T> > >& point_tree,V& AN){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() = f % prod.front();auto I_tree = point_tree.begin(),end_tree = point_tree.end();I_tree++;WH(I_tree != end_tree){auto I_residue = residue.begin(),end_residue = residue.end();auto I_node = I_tree->begin(),end_node = I_tree->end();WH(I_residue != end_residue){CO PO<T>& f = *I_node;I_node++;if(I_node != end_node){*(residue.insert(I_residue,zero)) = *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++){AN.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());WH(p_node->SZ() > 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() = 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;}
#define SET_MA_MULTIPOINT_EVALUATION(SAMPLE_NUM_MAX,POINT) point = 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_MA(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] = eval_odd[t] * sample[t]; } for(uint t = 0;t < REST_INTERVAL_LENGTH;t++){ sample.push_back(eval_odd[t + subinterval_num_max + 1] * eval_even[t]); }
TE <TY T>void SetIntervalEvaluation(C_UINT deg,CO T& t_start,C_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,MO(v) };ST PO<T> exp_inv{};for(uint d = exp_inv.SZ();d <= deg;d++){exp_inv[d] = (d % 2 == 0 ? PO<T>::factorial_inverse(d):- PO<T>::factorial_inverse(d));}f *= exp_inv;f.ReMORedundantZero();uint deg_f = f.SZ();if(deg_f == 0){eval = 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.SZ();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(C_UINT deg,CO T& t_start,C_UINT length,CO VE<MA<Y,X,T> >& sample,VE<MA<Y,X,T> >& eval){eval = 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,C_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 SZ = M_ref_y[x].SZ();if(deg < SZ){deg = SZ;}}}deg--;uint interval_length = 1;int exponent = 0;WH(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_MA_MULTIPOINT_EVALUATION(subinterval_num_max,t * interval_length);for(int e = 1;e < exponent;e++){MULTIPLY_SUBPRODUCT_OF_PRECURSIVE_MA(subinterval_num_max);subinterval_num_max *= 2;subinterval_length *= 2;}uint rest_interval_length = interval_num_max - subinterval_num_max;MULTIPLY_SUBPRODUCT_OF_PRECURSIVE_MA(rest_interval_length);for(uint t = 0;t <= interval_num_max;t++){v = 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_MA_MULTIPOINT_EVALUATION(rest_num_max,t + t_rest_start);for(uint t = 0;t <= rest_num_max;t++){v = 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 OP<(CO Query& q1,CO Query& q2){ RE q1.m_K < q2.m_K; }using MOD = Mod<P>;using MODX = PO<MOD>;class D{PU:MA<2,2,MODX> m_M;MODX m_pt;IN D() : m_M(),m_pt() {};IN D(MA<2,2,MODX>&& M,MODX&& pt):m_M(MO(M)) , m_pt(MO(pt)) {}IN D(CO D& d):m_M(d.m_M),m_pt(d.m_pt) {}IN D(D&& d):m_M(MO(d.m_M)),m_pt(MO(d.m_pt)) {}IN D& OP=(CO D& d) { m_M = d.m_M; m_pt = d.m_pt; RE *this; }IN D& OP=(D&& d) { m_M = MO(d.m_M); m_pt = MO(d.m_pt); RE *this; }IN D& OP*=(CO D& d) { m_M *= d.m_M; m_pt *= d.m_pt; RE *this; }};IN D OP*(CO D& d1,CO D& d2 ) { RE D(d1.m_M * d2.m_M,d1.m_pt * d2.m_pt); }
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 );
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 ){
static 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 );
LI<LI<D> > d_prod{};
LI<LI<int> > over_M{};
d_prod.push_front( LI<D>() );
over_M.push_front( LI<int>() );
LI<D>& d_prod_init = d_prod.front();
LI<int>& over_M_init = over_M.front();
ll k_start = 0;
FOR( t , 0 , T ){
Query& Qt = Q[t];
FOR( k , k_start , Qt.m_K ){
d_prod_init.push_front
( 
D(
MA<2,2,MODX>
{
X * CO_two - CO_two * k , X * k + CO_two_inv * ( ( 1 - k ) * k ) , 
MODX( one ) , MODX( zero )
}
, 
MODX( one ) ) );
over_M_init.push_front( 1 );
}
d_prod_init.push_front( D( MA<2,2,MODX>( 1 ) , X - Qt.m_N ) );
over_M_init.push_front( 0 );
k_start = Qt.m_K;
}
SetProductTree( d_prod );
SetProductTree( over_M );
LI<MA<2,1,MODX> > residue{};
residue.push_front( MA<2,1,MODX>( 1 ) );
auto itr_d_prod = d_prod.begin() , end_d_prod = d_prod.end();
auto itr_over_M = over_M.begin();
itr_d_prod++;
itr_over_M++;
MA<2,1,MODX> null{};
null.m_M.clear();
while( itr_d_prod != end_d_prod ){
auto itr_d_prod_node = itr_d_prod->begin() , end_d_prod_node = itr_d_prod->end();
auto itr_over_M_node = itr_over_M->begin();
FOR_ITR( residue , itr_residue , end_residue ){
MODX& pt_node_curr = itr_d_prod_node->m_pt;
int& over_M_node_curr = *itr_over_M_node;
itr_d_prod_node++;
itr_over_M_node++;
if( itr_d_prod_node != end_d_prod_node ){
residue.insert( itr_residue , over_M_node_curr == 0 ? MO( ( itr_d_prod_node->m_M * *itr_residue ) %= pt_node_curr ) : MA<2,1,MODX>( null ) );
if( *itr_over_M_node == 0 ){
*itr_residue %= itr_d_prod_node->m_pt;
}
itr_d_prod_node++;
itr_over_M_node++;
} else {
break;
}
}
itr_d_prod++;
itr_over_M++;
}
static ll answer[bound_T];
auto itr_over_M_node = over_M.back().begin();
auto itr_residue = residue.begin();
FOREQINV( t , T - 1 , 0 ){
while( *itr_over_M_node == 1 ){
itr_over_M_node++;
itr_residue++;
}
answer[Q[t].m_t] = itr_residue->m_M[0][0][0].Represent();
itr_over_M_node++;
itr_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 ) ,
MODX( one ) , MODX( zero )
};
MA<2,1,MOD> v_copy{ v };
SetPRecursiveMAAction( MNX , v_copy , K );
cout << v_copy.m_M[0][0] << "\n";
}
}
}
QUIT;
}
yukicoder

結果

テストケース

ソースコード
