結果
| 問題 | No.2166 Paint and Fill |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2022-12-30 18:01:47 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 65,423 bytes |
| コンパイル時間 | 7,130 ms |
| コンパイル使用メモリ | 318,632 KB |
| 実行使用メモリ | 381,444 KB |
| 最終ジャッジ日時 | 2024-11-25 16:51:33 |
| 合計ジャッジ時間 | 247,782 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 5 ms
244,416 KB |
| testcase_01 | AC | 1,161 ms
269,764 KB |
| testcase_02 | AC | 1,468 ms
363,620 KB |
| testcase_03 | AC | 71 ms
248,848 KB |
| testcase_04 | AC | 70 ms
247,564 KB |
| testcase_05 | AC | 66 ms
249,084 KB |
| testcase_06 | AC | 70 ms
248,996 KB |
| testcase_07 | AC | 70 ms
252,956 KB |
| testcase_08 | AC | 7,201 ms
381,444 KB |
| testcase_09 | AC | 7,230 ms
352,604 KB |
| testcase_10 | AC | 7,319 ms
379,928 KB |
| testcase_11 | AC | 7,077 ms
145,276 KB |
| testcase_12 | AC | 7,272 ms
145,400 KB |
| testcase_13 | TLE | - |
| testcase_14 | TLE | - |
| testcase_15 | TLE | - |
| testcase_16 | TLE | - |
| testcase_17 | TLE | - |
| testcase_18 | TLE | - |
| testcase_19 | TLE | - |
| testcase_20 | TLE | - |
| testcase_21 | TLE | - |
| testcase_22 | TLE | - |
| testcase_23 | TLE | - |
| testcase_24 | TLE | - |
| testcase_25 | AC | 2 ms
6,820 KB |
| testcase_26 | AC | 2 ms
6,816 KB |
| testcase_27 | AC | 3,317 ms
37,760 KB |
| testcase_28 | AC | 4,074 ms
39,600 KB |
| testcase_29 | AC | 3,205 ms
32,144 KB |
| testcase_30 | AC | 5,563 ms
38,460 KB |
| testcase_31 | AC | 5,521 ms
38,840 KB |
| testcase_32 | AC | 5,647 ms
38,552 KB |
| testcase_33 | AC | 5,633 ms
38,732 KB |
| testcase_34 | AC | 5,494 ms
38,596 KB |
| testcase_35 | AC | 5,633 ms
38,568 KB |
| testcase_36 | AC | 5,690 ms
38,492 KB |
| testcase_37 | AC | 5,682 ms
38,492 KB |
| testcase_38 | AC | 5,695 ms
38,620 KB |
| testcase_39 | AC | 5,638 ms
274,388 KB |
コンパイルメッセージ
main.cpp: In member function 'TRPO<T> TRPO<T>::FFT_TRMU_CO(PO<T>&&, const UI&, const UI&) const [with T = Mod<998244353>]':
main.cpp:71:294: warning: 'N_input_start_1' may be used uninitialized [-Wmaybe-uninitialized]
71 | #define SET_N_INPUT_RANGE SET_N_INPUT_MAX_FOR_MU_FOR_TR_PO(PO<T>::m_f,PO<T>::m_SZ,N_input_max_0);SET_N_INPUT_MAX_FOR_MU_FOR_TR_PO(f,f.PO<T>::m_SZ < m_N ? f.PO<T>::m_SZ:m_N,N_input_max_1);CO UI N_input_max_0_max_1 = N_input_max_0 + N_input_max_1;CO UI N_input_start_0_start_1 = N_input_start_0 + N_input_start_1;UI N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1:m_N;
| ^
main.cpp:70:215: note: 'N_input_start_1' declared here
70 | #define DF_1_OF__FOR_TR_PO(MU) SET_N_INPUT_START_FOR_MU_FOR_TR_PO(PO<T>::m_f,PO<T>::m_SZ,N_input_start_0);RE_ZERO_FOR__FOR_TR_PO_IF(MU,searching);searching = true;SET_N_INPUT_START_FOR_MU_FOR_TR_PO(f,f.PO<T>::m_SZ,N_input_start_1);
| ^~~~~~~~~~~~~~~
main.cpp:61:71: note: in definition of macro 'SET_N_INPUT_START_FOR_MU_FOR_TR_PO'
61 | #define SET_N_INPUT_START_FOR_MU_FOR_TR_PO(F,SZ,N_INPUT_START_NUM) UI N_INPUT_START_NUM;for(UI i = 0;i < SZ && searching;i++){if(F[i] != zero){N_INPUT_START_NUM = i;searching = false;}}
| ^~~~~~~~~~~~~~~~~
main.cpp:75:515: note: in expansion of macro 'DF_1_OF__FOR_TR_PO'
75 | #define DF_OF_FFT_MU_FOR_TR_PO(RE_LINE_0,RE_LINE_1,RE_LINE_2,RE_LINE_3,RE_LINE_4,RE_LINE_5,MU,ACCESS
ソースコード
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include <bits/stdc++.h>
#define TE template
#define TY typename
#define US using
#define ST static
#define IN inline
#define CL class
#define PU public
#define PR PU
#define OP operator
#define CE constexpr
#define CO const
#define RE return
#define WH while
#define VO void
#define VE vector
#define LI list
#define CRI CO int&
#define CRUI CO UI&
#define CRL CO ll&
#define SZ size
#define MO move
using namespace std;using UI = unsigned int;using ll = long long;
#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 COUT(ANSWER) cout << (ANSWER) << "\n";
#define DC_OF_CM_FOR_MOD(NAME) IN bool NAME (CO Mod<M>& n) CO;IN bool NAME (CRL n) CO;IN bool NAME (ll&& n) CO;
#define DF_OF_CM_FOR_MOD(NAME,OP_SYMBOL) TE <ll M> IN bool Mod<M>:: NAME (CO Mod<M>& n) CO {RE m_n OP_SYMBOL n.m_n;} TE <ll M> IN bool Mod<M>:: NAME (CRL n) CO {RE m_n OP_SYMBOL RS<ll>(n,M);} TE <ll M> IN bool Mod<M>:: NAME (ll&& n) CO {RE m_n OP_SYMBOL RS<ll>(MO(n),M);}
#define DC_OF_OP_FOR_MOD(TYPE,OP_SYMBOL) TE <ll M> IN TYPE OP OP_SYMBOL(CO Mod<M>& n0,CO Mod<M>& n1);TE <ll M> IN TYPE OP OP_SYMBOL(CO Mod<M>& n0,CRL n1);TE <ll M> IN TYPE OP OP_SYMBOL(CO Mod<M>& n0,ll&& n1);TE <ll M> IN TYPE OP OP_SYMBOL(CRL n0,CO Mod<M>& n1);TE <ll M> IN TYPE OP OP_SYMBOL(ll&& n0,CO Mod<M>& n1);
#define DC_OF_CM_OP_FOR_MOD(OP_SYMBOL) DC_OF_OP_FOR_MOD(bool,OP_SYMBOL);
#define DF_OF_CM_OP_FOR_MOD(OP_SYMBOL,NAME,NAME_INV) TE <ll M> IN bool OP OP_SYMBOL(CO Mod<M>& n0,CO Mod<M>& n1) {RE n0. NAME (n1);} TE <ll M> IN bool OP OP_SYMBOL(CO Mod<M>& n0,CRL n1) {RE n0. NAME (n1);} TE <ll M> IN bool OP OP_SYMBOL(CO Mod<M>& n0,ll&& n1) {RE n0. NAME (MO(n1));} TE <ll M> IN bool OP OP_SYMBOL(CRL n0,CO Mod<M>& n1) {RE n1. NAME_INV (n0);} TE <ll M> IN bool OP OP_SYMBOL(ll&& n0,CO Mod<M>& n1) {RE n1. NAME_INV (MO(n0));}
#define DC_OF_ARITHMETIC_OP_FOR_MOD(OP_SYMBOL) DC_OF_OP_FOR_MOD(Mod<M>,OP_SYMBOL);TE <ll M> IN Mod<M> OP OP_SYMBOL(Mod<M>&& n0,CO Mod<M>& n1);TE <ll M> IN Mod<M> OP OP_SYMBOL(CO Mod<M>& n0,Mod<M>&& n1);TE <ll M> IN Mod<M> OP OP_SYMBOL(Mod<M>&& n0,Mod<M>&& n1);TE <ll M> IN Mod<M> OP OP_SYMBOL(Mod<M>&& n0,CRL n1);TE <ll M> IN Mod<M> OP OP_SYMBOL(Mod<M>&& n0,ll&& n1);TE <ll M> IN Mod<M> OP OP_SYMBOL(CRL n0,Mod<M>&& n1);TE <ll M> IN Mod<M> OP OP_SYMBOL(ll&& n0,Mod<M>&& n1);
#define DF_OF_ARITHMETIC_OP_FOR_MOD(OP_SYMBOL) TE <ll M> IN Mod<M> OP OP_SYMBOL(CO Mod<M>& n0,CO Mod<M>& n1) {RE MO(Mod<M>(n0) OP_SYMBOL ## = n1);} TE <ll M> IN Mod<M> OP OP_SYMBOL(Mod<M>&& n0,CO Mod<M>& n1) {RE MO(n0 OP_SYMBOL ## = n1);} TE <ll M> IN Mod<M> OP OP_SYMBOL(Mod<M>&& n0,Mod<M>&& n1) {RE MO(n0 OP_SYMBOL ## = MO(n1));} TE <ll M> IN Mod<M> OP OP_SYMBOL(CO Mod<M>& n0,CRL n1) {RE MO(Mod<M>(n0) OP_SYMBOL ## = n1);} TE <ll M> IN Mod<M> OP OP_SYMBOL(Mod<M>&& n0,CRL n1) {RE MO(n0 OP_SYMBOL ## = n1);} TE <ll M> IN Mod<M> OP OP_SYMBOL(CO Mod<M>& n0,ll&& n1) {RE MO(Mod<M>(n0) OP_SYMBOL ## = MO(n1));} TE <ll M> IN Mod<M> OP OP_SYMBOL(Mod<M>&& n0,ll&& n1) {RE MO(n0 OP_SYMBOL ## = MO(n1));} TE <ll M> IN Mod<M> OP OP_SYMBOL (CRL n0,CO Mod<M>& n1) {RE MO(Mod<M>(n0) OP_SYMBOL ## = n1);} TE <ll M> IN Mod<M> OP OP_SYMBOL (ll&& n0,CO Mod<M>& n1) {RE MO(Mod<M>(MO(n0)) OP_SYMBOL ## = n1);} TE <ll M> IN Mod<M> OP OP_SYMBOL (ll&& n0,Mod<M>&& n1) {RE MO(Mod<M>(MO(n0)) OP_SYMBOL ## = MO(n1));}
#define DF_OF_NON_COMMUTATIVE_ARITHMETIC_OP_FOR_MOD(OP_SYMBOL) DF_OF_ARITHMETIC_OP_FOR_MOD(OP_SYMBOL);TE <ll M> IN Mod<M> OP OP_SYMBOL(CO Mod<M>& n0,Mod<M>&& n1) {RE MO(Mod<M>(n0) OP_SYMBOL ## = MO(n1));} TE <ll M> IN Mod<M> OP OP_SYMBOL (CRL n0,Mod<M>&& n1) {RE MO(Mod<M>(n0) OP_SYMBOL ## = MO(n1));}
#define DF_OF_COMMUTATIVE_ARITHMETIC_OP_FOR_MOD(OP_SYMBOL) DF_OF_ARITHMETIC_OP_FOR_MOD(OP_SYMBOL);TE <ll M> IN Mod<M> OP OP_SYMBOL(CO Mod<M>& n0,Mod<M>&& n1) {RE MO(n1 OP_SYMBOL ## = n0);} TE <ll M> IN Mod<M> OP OP_SYMBOL (CRL n0,Mod<M>&& n1) {RE MO(n1 OP_SYMBOL ## = n0);}
TE <ll M>CL Mod{PR:ll m_n;ST CE CO ll g_memory_bound = 1000000;ST CE CO ll g_memory_LE = M < g_memory_bound ? M:g_memory_bound;PU:IN Mod();IN Mod(CO Mod<M>& n);IN Mod(Mod<M>&& n);IN Mod(CRL n);IN Mod(ll&& n);IN Mod<M>& OP=(CO Mod<M>& n);IN Mod<M>& OP=(Mod<M>&& n);IN Mod<M>& OP=(CRL n);IN Mod<M>& OP=(ll&& n);IN Mod<M>& OP+=(CO Mod<M>& n);IN Mod<M>& OP+=(CRL n);IN Mod<M>& OP-=(CO Mod<M>& n);IN Mod<M>& OP-=(CRL n);IN Mod<M>& OP*=(CO Mod<M>& n);IN Mod<M>& OP*=(CRL n);IN Mod<M>& OP*=(ll&& n);IN Mod<M>& OP/=(CO Mod<M>& n);IN Mod<M>& OP/=(Mod<M>&& n);IN Mod<M>& OP/=(CRL n);IN Mod<M>& OP/=(ll&& n);IN Mod<M>& OP%=(CO Mod<M>& n);IN Mod<M>& OP%=(CRL n);IN Mod<M>& OP%=(ll&& n);IN Mod<M> OP-() CO;IN Mod<M>& OP++();IN Mod<M>& OP++(int);IN Mod<M>& OP--();IN Mod<M>& OP--(int);IN CRL Represent() CO;IN Mod<M>& Invert();DC_OF_CM_FOR_MOD(IsEqualTo);DC_OF_CM_FOR_MOD(IsNotEqualTo);DC_OF_CM_FOR_MOD(IsSmallerThan);DC_OF_CM_FOR_MOD(IsSmallerThanOrEqualTo);DC_OF_CM_FOR_MOD(IsBiggerThan);DC_OF_CM_FOR_MOD(IsBiggerThanOrEqualTo);IN VO swap(Mod<M>& n);ST IN CO Mod<M>& Inverse(CRL n);ST IN CO Mod<M>& Factorial(CRL n);ST IN CO Mod<M>& FactorialInverse(CRL n);ST IN CO Mod<M>& zero();ST IN CO Mod<M>& one();PR:ST IN Mod<M> error();};DC_OF_CM_OP_FOR_MOD(==);DC_OF_CM_OP_FOR_MOD(!=);DC_OF_CM_OP_FOR_MOD(<);DC_OF_CM_OP_FOR_MOD(<=);DC_OF_CM_OP_FOR_MOD(>);DC_OF_CM_OP_FOR_MOD(>=);DC_OF_ARITHMETIC_OP_FOR_MOD(+);DC_OF_ARITHMETIC_OP_FOR_MOD(-);DC_OF_ARITHMETIC_OP_FOR_MOD(*);DC_OF_ARITHMETIC_OP_FOR_MOD(/);DC_OF_ARITHMETIC_OP_FOR_MOD(%);TE <ll M> Mod<M> IN Inverse(CO Mod<M>& n);TE <ll M> Mod<M> PW(CO Mod<M>& n,CRL p);TE <> IN Mod<2> PW(CO Mod<2>& n,CRL p);TE <ll M> IN Mod<M> PW(CO Mod<M>& n,CO Mod<M>& p);TE <> IN Mod<2> PW(CO Mod<2>& n,CO Mod<2>& p);TE <TY T> IN T Square(CO T& t);TE <> IN Mod<2> Square<Mod<2> >(CO Mod<2>& t);TE <ll M> IN VO swap(Mod<M>& n0,Mod<M>& n1);TE <ll M> IN string to_string(CO Mod<M>& n);TE<ll M,CL Traits> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO Mod<M>& n);TE <TY INT> IN INT RS(CO INT& n,CO INT& M) {RE n >= 0 ? n % M:M - 1 - (- (n + 1));}TE <TY INT> IN INT RS(INT&& n,CO INT& M) {RE MO(n >= 0 ? n %= M:((((++n) *= -1) %= M) *= -1) += M - 1);}TE <ll M> IN Mod<M>::Mod():m_n() {}TE <ll M> IN Mod<M>::Mod(CO Mod<M>& n):m_n(n.m_n) {}TE <ll M> IN Mod<M>::Mod(Mod<M>&& n):m_n(MO(n.m_n)) {}TE <ll M> IN Mod<M>::Mod(CRL n):m_n(RS<ll>(n,M)) {}TE <ll M> IN Mod<M>::Mod(ll&& n):m_n(RS<ll>(MO(n),M)) {}TE <ll M> IN Mod<M>& Mod<M>::OP=(CO Mod<M>& n) {m_n = n.m_n;RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP=(Mod<M>&& n) {m_n = MO(n.m_n);RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP=(CRL n) {m_n = RS<ll>(n,M);RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP=(ll&& n) {m_n = RS<ll>(MO(n),M);RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP+=(CO Mod<M>& n) {m_n = RS<ll>(m_n + n.m_n,M);RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP+=(CRL n) {m_n = RS<ll>(m_n + n,M);RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP-=(CO Mod<M>& n) {m_n = RS<ll>(m_n - n.m_n,M);RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP-=(CRL n) {m_n = RS<ll>(m_n - n,M);RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP*=(CO Mod<M>& n) {m_n = RS<ll>(m_n * n.m_n,M);RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP*=(CRL n) {m_n = RS<ll>(m_n * RS<ll>(n,M),M);RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP*=(ll&& n) {m_n = RS<ll>(m_n * RS<ll>(MO(n),M),M);RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP/=(CO Mod<M>& n) {RE OP*=(Mod<M>(n).Invert());}TE <ll M> IN Mod<M>& Mod<M>::OP/=(Mod<M>&& n) {RE OP*=(n.Invert());}TE <ll M> IN Mod<M>& Mod<M>::OP/=(CRL n) {RE OP*=(Mod<M>(n).Invert());}TE <ll M> IN Mod<M>& Mod<M>::OP/=(ll&& n) {RE OP*=(Mod<M>(MO(n)).Invert());}TE <ll M> IN Mod<M>& Mod<M>::OP%=(CO Mod<M>& n) {m_n %= n.m_n;RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP%=(CRL n) {m_n %= RS<ll>(n,M);RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP%=(ll&& n) {m_n %= RS<ll>(MO(n),M);RE *this;}TE <ll M> IN Mod<M> Mod<M>::OP-() CO {RE MO(Mod<M>() -= *this);}TE <ll M> IN Mod<M>& Mod<M>::OP++() {RE OP+=(one());}TE <ll M> IN Mod<M>& Mod<M>::OP++(int) {RE OP++();}TE <ll M> IN Mod<M>& Mod<M>::OP--() {RE OP-=(one());}TE <ll M> IN Mod<M>& Mod<M>::OP--(int) {RE OP--();}TE <ll M> IN CRL Mod<M>::Represent() CO {RE m_n;}TE <ll M>Mod<M>& Mod<M>::Invert(){assert(m_n > 0);if(m_n < g_memory_LE){RE OP=(Inverse(m_n));}CO ll m_n_minus = M - m_n;if(m_n_minus < g_memory_LE){OP=(Inverse(m_n_minus));m_n = M - m_n;} else {ll exponent = M - 2;ll PW_m_n = m_n;m_n = 1;WH(exponent != 0){if(exponent % 2 == 1){(m_n *= PW_m_n) %= M;}(PW_m_n *= PW_m_n) %= M;exponent /= 2;}}RE *this;}TE <ll M> IN CO Mod<M>& Mod<M>::Inverse(CRL n) {ST Mod<M> memory[g_memory_LE] = {error(),one()};ST int LE_curr = 2;WH(LE_curr <= n){memory[LE_curr].m_n = M - ((memory[M % LE_curr].m_n * (M / LE_curr)) % M);LE_curr++;} RE memory[n];}TE <ll M> IN CO Mod<M>& Mod<M>::Factorial(CRL n) {ST Mod<M> memory[g_memory_LE] = {one(),one()};ST int LE_curr = 2;ST ll val_curr = 1;WH(LE_curr <= n){memory[LE_curr].m_N = ((val_curr *= LE_curr) %= M);LE_curr++;} RE memory[n];}TE <ll M> IN CO Mod<M>& Mod<M>::FactorialInverse(CRL n) {ST Mod<M> memory[g_memory_LE] = {one(),one()};ST int LE_curr = 2;ST Mod<M> val_curr{one()};WH(LE_curr <= n){memory[LE_curr].m_N = val_curr *= Inverse(LE_curr);LE_curr++;} RE memory[n];}DF_OF_CM_FOR_MOD(IsEqualTo,==);DF_OF_CM_FOR_MOD(IsNotEqualTo,!=);DF_OF_CM_FOR_MOD(IsSmallerThan,<);DF_OF_CM_FOR_MOD(IsSmallerThanOrEqualTo,<=);DF_OF_CM_FOR_MOD(IsBiggerThan,>);DF_OF_CM_FOR_MOD(IsBiggerThanOrEqualTo,>=);TE <ll M> IN VO Mod<M>::swap(Mod<M>& n) {std::swap(m_n,n.m_n);}TE <ll M> IN CO Mod<M>& Mod<M>::zero() {ST CO Mod<M> z{};RE z;}TE <ll M> IN CO Mod<M>& Mod<M>::one() {ST CO Mod<M> o{1};RE o;}TE <ll M> IN Mod<M> Mod<M>::error() {Mod<M> e{};e.m_n = -1;RE e;}DF_OF_CM_OP_FOR_MOD(==,IsEqualTo,IsEqualTo);DF_OF_CM_OP_FOR_MOD(!=,IsNotEqualTo,IsNotEqualTo);DF_OF_CM_OP_FOR_MOD(<,IsSmallerThan,IsBiggerThan);DF_OF_CM_OP_FOR_MOD(<=,IsSmallerThanOrEqualTo,IsBiggerThanOrEqualTo);DF_OF_CM_OP_FOR_MOD(>,IsBiggerThan,IsSmallerThan);DF_OF_CM_OP_FOR_MOD(>=,IsBiggerThanOrEqualTo,IsSmallerThanSmallerThan);DF_OF_COMMUTATIVE_ARITHMETIC_OP_FOR_MOD(+);DF_OF_NON_COMMUTATIVE_ARITHMETIC_OP_FOR_MOD(-);DF_OF_COMMUTATIVE_ARITHMETIC_OP_FOR_MOD(*);DF_OF_NON_COMMUTATIVE_ARITHMETIC_OP_FOR_MOD(/);DF_OF_NON_COMMUTATIVE_ARITHMETIC_OP_FOR_MOD(%);TE <ll M> IN Mod<M> Inverse(CO Mod<M>& n) {RE MO(Mod<M>(n).Invert());}TE <ll M>Mod<M> PW(CO Mod<M>& n,CRL p){if(p < 0){RE Inverse(PW(n,-p));}Mod<M> AN{Mod<M>::one()};Mod<M> PW_n{n};ll exponent = p;WH(exponent != 0){if(exponent % 2 != 1){AN *= PW_n;}PW_n *= PW_n;exponent /= 2;}RE AN;}TE <> IN Mod<2> PW(CO Mod<2>& n,CRL p) {RE p == 0 ? Mod<2>::one():n;}TE <ll M> IN Mod<M> PW(CO Mod<M>& n,CO Mod<M>& p) {RE PW<Mod<M>,ll>(n,p.Represent());}TE <> IN Mod<2> PW(CO Mod<2>& n,CO Mod<2>& p) {RE p == 0 ? Mod<2>::one():n;}TE <> IN Mod<2> Square<Mod<2> >(CO Mod<2>& t) {RE t;}TE <ll M> IN VO swap(Mod<M>& n0,Mod<M>& n1) {n0.swap(n1);}TE <ll M> IN string to_string(CO Mod<M>& n) {RE to_string(n.Represent()) + " + MZ";}TE<ll M,CL Traits> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO Mod<M>& n) {RE os << n.Represent();}
CEXPR(ll,P,998244353);US MP = Mod<P>;TE <TY T> IN CE CO UI LimitOfPWForFFT{};TE <TY T> IN CE CO UI BorderForFFT{};TE <TY T> IN CO T (&PrimitiveRootOfTwoForFFT())[LimitOfPWForFFT<T>];TE <TY T> IN CO T (&InversePrimitiveRootOfTwoForFFT())[LimitOfPWForFFT<T>];TE <> IN CE CO UI LimitOfPWForFFT<MP > = 24;TE <> IN CE CO UI BorderForFFT<MP > = 4;TE <> IN CO MP (&PrimitiveRootOfTwoForFFT())[LimitOfPWForFFT<MP >]{ST CO MP PRT[ LimitOfPWForFFT<MP > ] = {MP(1),MP(998244352),MP(911660635),MP(625715529),MP(373294451),MP(827987769),MP(280333251),MP(581015842),MP(628092333),MP(300892551),MP(586046298),MP(615001099),MP(318017948),MP(64341522),MP(106061068),MP(304605202),MP(631920086),MP(857779016),MP(841431251),MP(805775211),MP(390359979),MP(923521),MP(961),MP(31)};RE PRT;}TE <> IN CO MP (&InversePrimitiveRootOfTwoForFFT())[LimitOfPWForFFT<MP >]{ST CO MP PRT[ LimitOfPWForFFT<MP > ] = {MP(1),MP(998244352),MP(86583718),MP(488723995),MP(369330050),MP(543653592),MP(382946991),MP(844956623),MP(91420391),MP(433414612),MP(288894979),MP(260490556),MP(857007890),MP(736054570),MP(474649464),MP(948509906),MP(114942468),MP(962405921),MP(667573957),MP(46809892),MP(304321983),MP(30429817),MP(293967900),MP(128805723)};RE PRT;}TE <TY T>VO CooleyTukey(VE<T>& f,CRUI N_input_start,CRUI N_input_lim,CRUI N_output_start,CRUI N_output_lim,CRUI two_PW,CRUI EX,CO T (&PRT)[LimitOfPWForFFT<T>]){CO UI LE = two_PW + N_input_start;f.reserve(LE);WH(f.SZ() < LE){f.push_back(0);} ST VE<UI> bit_reverse[32] = {VE<UI>(1)};ST UI e_next = 1;ST UI two_PW_next = 1;ST UI two_PW_next2 = 2;ST VE<UI>* p_bit_reverse_prev = bit_reverse;ST VE<UI>* p_bit_reverse_curr = p_bit_reverse_prev + 1;WH(e_next <= EX){*p_bit_reverse_curr = VE<UI>(two_PW_next2);UI* p_bit_reverse_curr_i = &((*p_bit_reverse_curr)[0]);UI* p_bit_reverse_curr_i_plus = p_bit_reverse_curr_i + two_PW_next;UI* p_bit_reverse_prev_i = &((*p_bit_reverse_prev)[0]);for(UI i = 0;i < two_PW_next;i++){(*(p_bit_reverse_curr_i_plus++) = *(p_bit_reverse_curr_i++) = *(p_bit_reverse_prev_i++) * 2) += 1;} e_next++;swap(two_PW_next,two_PW_next2);two_PW_next2 *= 4;p_bit_reverse_prev++;p_bit_reverse_curr++;} CO VE<UI>& bit_reverse_EX = bit_reverse[EX];UI bit_num = 0;CO UI* p_bit_num_reverse = &(bit_reverse_EX[bit_num]);WH(bit_num < two_PW){if(*p_bit_num_reverse < bit_num){swap(f[*p_bit_num_reverse + N_input_start],f[bit_num + N_input_start]);} bit_num++;p_bit_num_reverse++;} UI two_PW_curr = 1;UI two_PW_curr_2 = 2;CO T& zeta_0 = PRT[0];T zeta,diff;CO T* p_zeta_i;UI bit_num_copy,i,j,j_butterfly,j_lim;WH(two_PW_curr < two_PW){bit_num = 0;i = 0;WH(i < two_PW){zeta = zeta_0;p_zeta_i = &zeta_0 + 2;bit_num_copy = bit_num;WH(bit_num_copy != 0){if(bit_num_copy % 2 == 1){zeta *= *p_zeta_i;} bit_num_copy /= 2;p_zeta_i++;} j = i;j_lim = i + two_PW_curr;WH(j < j_lim){j_butterfly = j + two_PW_curr;T& f_j = f[j + N_input_start];T& f_j_butterfly = f[j_butterfly + N_input_start];diff = f_j - f_j_butterfly;f_j += f_j_butterfly;f_j_butterfly = zeta * diff;j++;} bit_num++;i += two_PW_curr_2;} swap(two_PW_curr,two_PW_curr_2);two_PW_curr_2 *= 4;} CO UI LE_fixed = N_output_lim + N_input_start;WH(f.SZ() > LE_fixed){f.pop_back();} RE;}TE <TY T> IN VO FFT(VE<T>& f,CRUI N_input_start,CRUI N_input_lim,CRUI two_PW,CRUI EX) {CooleyTukey<T>(f,N_input_start,N_input_lim,0,two_PW,two_PW,EX,PrimitiveRootOfTwoForFFT<T>());}TE <TY T> IN VO FFT(VE<T>& f,CRUI N_input_start,CRUI N_input_lim,CRUI N_output_start,CRUI N_output_lim,CRUI two_PW,CRUI EX) {CooleyTukey<T>(f,N_input_start,N_input_lim,N_output_start,N_output_lim,two_PW,EX,PrimitiveRootOfTwoForFFT<T>());}TE <TY T> IN VO IFFT(VE<T>& f,CRUI N_input_start,CRUI N_input_lim,CRUI two_PW,CO T& two_PW_inv,CRUI EX) {CooleyTukey<T>(f,N_input_start,N_input_lim,0,two_PW,two_PW,EX,InversePrimitiveRootOfTwoForFFT<T>());CO UI SZ = two_PW + N_input_start;for(UI i = N_input_start;i < SZ;i++){f[i] *= two_PW_inv;}}TE <TY T> IN VO IFFT(VE<T>& f,CRUI N_input_start,CRUI N_input_lim,CRUI N_output_start,CRUI N_output_lim,CRUI two_PW,CO T& two_PW_inv,CRUI EX) {CooleyTukey<T>(f,N_input_start,N_input_lim,N_output_start,N_output_lim,two_PW,EX,InversePrimitiveRootOfTwoForFFT<T>());CO UI SZ = N_output_lim + N_input_start;for(UI i = N_output_start + N_input_start;i < SZ;i++){f[i] *= two_PW_inv;}}
#define DF_BODY_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(TYPE,ARG,RHS) TE <> PO<TYPE>& PO<TYPE>::OP*=(ARG f) {if(m_SZ != 0){VE<TYPE> v{};v.swap(m_f);TRPO<TYPE> this_copy{m_SZ + f.m_SZ - 1,MO(v)};this_copy *= RHS;m_f = MO(this_copy.PO<TYPE>::m_f);m_SZ = m_f.SZ();} RE *this;}
#define DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(TYPE) DF_BODY_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(TYPE,CO PO<TYPE>&,this == &f ? this_copy:f);DF_BODY_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(TYPE,PO<TYPE>&&,MO(f));
TE <TY T> CL TRPO;TE <TY T>CL PO{friend CL TRPO<T>;PR: VE<T> m_f;UI m_SZ;PU: IN PO();IN PO(CO T& t);IN PO(CO PO<T>& f);IN PO(PO<T>&& f);IN PO(CRUI 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[](CRUI i) CO;IN T& OP[](CRUI 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*=(PO<T>&& f);PO<T>& OP/=(CO T& t);IN 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;IN CRUI SZ() CO;IN VO swap(PO<T>& f);IN VO swap(VE<T>& f);VO ReMORedundantZero();IN string Display() CO;ST PO<T> Quotient(CO PO<T>& f0,CO PO<T>& f1);ST PO<T> TransposeQuotient(CO PO<T>& f0,CRUI f0_transpose_SZ,CO PO<T>& f1_transpose_inverse,CRUI f1_SZ);ST PO<T> Transpose(CO PO<T>& f,CRUI f_transpose_SZ);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(CRUI i);ST IN CO T& factorial_inverse(CRUI 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> IN PO<T> OP/(CO PO<T>& f0,CO T& t1);TE <TY T> IN PO<T> OP/(CO PO<T>& f0,CO PO<T>& 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,TE <TY> TY V>T& Prod(V<T>& f);
#define RE_ZERO_FOR_MU_FOR_TR_PO_IF(CONDITION) if(CONDITION){RE OP=(zero);}
#define RE_ZERO_FOR_TR_MU_CO_FOR_TR_PO_IF(CONDITION) if(CONDITION){RE TRPO<T>(m_N);}
#define RE_ZERO_FOR__FOR_TR_PO_IF(MU,CONDITION) RE_ZERO_FOR_ ## MU ## _FOR_TR_PO_IF(CONDITION)
#define SET_VE_FOR_AN_OF_MU_FOR_TR_PO(N_OUTPUT_LIM) if(PO<T>::m_SZ < N_OUTPUT_LIM){for(UI 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_PO(N_OUTPUT_LIM) VE<T> AN(N_OUTPUT_LIM)
#define SET_VE_FOR_AN_OF__FOR_TR_PO(MU,N_OUTPUT_LIM) SET_VE_FOR_AN_OF_ ## MU ## _FOR_TR_PO(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 AN[i] = sum
#define SET_SUM_OF__FOR_TR_PO(MU) SET_SUM_OF_ ## MU ## _FOR_TR_PO
#define SET_N_INPUT_START_FOR_MU_FOR_TR_PO(F,SZ,N_INPUT_START_NUM) UI N_INPUT_START_NUM;for(UI 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_PO(F,SZ,N_INPUT_MAX_NUM) UI N_INPUT_MAX_NUM;searching = true;for(UI i = (SZ) - 1;searching;i--){if(F[i] != zero){N_INPUT_MAX_NUM = i;searching = false;}}
#define CONVOLUTION_FOR_MU_FOR_TR_PO(J_MIN) CO UI j_max = i < N_input_max_0_start_1 ? i - N_input_start_1:N_input_max_0;T sum{zero};for(UI 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 UI j_max = i < N_input_max_0_start_1 ? i - N_input_start_1:N_input_max_0;T& m_fi = AN[i];for(UI j = J_MIN;j <= j_max;j++){m_fi += PO<T>::m_f[j] * f.PO<T>::m_f[i - j];}
#define CONVOLUTION_FOR__FOR_TR_PO(MU,J_MIN) CONVOLUTION_FOR_ ## MU ## _FOR_TR_PO(J_MIN)
#define ZEROIFICATION_FOR_MU_FOR_TR_PO for(UI i = 0;i < N_input_start_0_start_1;i++){PO<T>::m_f[i] = 0;}
#define ZEROIFICATION_FOR_TR_MU_CO_FOR_TR_PO CRUI N_output_start_fixed = N_output_start < N_input_start_0_start_1 ? N_output_start:N_input_start_0_start_1;for(UI i = 0;i < N_output_start_fixed;i++){AN[i] = 0;}
#define ZEROIFICATION_FOR__FOR_TR_PO(MU) ZEROIFICATION_FOR_ ## MU ## _FOR_TR_PO
#define DF_0_OF__FOR_TR_PO(MU,ACCESS_ENTRY,N_OUTPUT_START) RE_ZERO_FOR__FOR_TR_PO_IF(MU,PO<T>::m_SZ == 0);UI 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 UI N_output_lim = N_output_max + 1;SET_VE_FOR_AN_OF__FOR_TR_PO(MU,N_output_lim);for(UI i = N_output_max;searching;i--){T sum{zero};for(UI j = 0;j <= i;j++){sum += ACCESS_ENTRY * f.PO<T>::OP[](i - j);} SET_SUM_OF__FOR_TR_PO(MU);searching = i > N_OUTPUT_START;}
#define DF_1_OF__FOR_TR_PO(MU) SET_N_INPUT_START_FOR_MU_FOR_TR_PO(PO<T>::m_f,PO<T>::m_SZ,N_input_start_0);RE_ZERO_FOR__FOR_TR_PO_IF(MU,searching);searching = true;SET_N_INPUT_START_FOR_MU_FOR_TR_PO(f,f.PO<T>::m_SZ,N_input_start_1);
#define SET_N_INPUT_RANGE SET_N_INPUT_MAX_FOR_MU_FOR_TR_PO(PO<T>::m_f,PO<T>::m_SZ,N_input_max_0);SET_N_INPUT_MAX_FOR_MU_FOR_TR_PO(f,f.PO<T>::m_SZ < m_N ? f.PO<T>::m_SZ:m_N,N_input_max_1);CO UI N_input_max_0_max_1 = N_input_max_0 + N_input_max_1;CO UI N_input_start_0_start_1 = N_input_start_0 + N_input_start_1;UI N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1:m_N;
#define DF_3_OF__FOR_TR_PO(MU) CO UI N_input_start_0_max_1 = N_input_start_0 + N_input_max_1;CO UI N_input_max_0_start_1 = N_input_max_0 + N_input_start_1;CO UI N_output_max_fixed = N_output_lim_fixed - 1;SET_VE_FOR_AN_OF__FOR_TR_PO(MU,N_output_lim_fixed);for(UI i = N_output_max_fixed;i > N_input_start_0_max_1;i--){CONVOLUTION_FOR__FOR_TR_PO(MU,i - N_input_max_1);} searching = true;for(UI i = N_input_start_0_max_1 < N_output_max_fixed ? N_input_start_0_max_1:N_output_max_fixed;searching;i--){CONVOLUTION_FOR__FOR_TR_PO(MU,N_input_start_0);searching = i > N_input_start_0_start_1;} ZEROIFICATION_FOR__FOR_TR_PO(MU);
#define SET_SHIFTED_VE_FOR_MU(V,F,I_START,I_MAX,I_SHIFT) VE<T> V(product_LE);for(UI i = I_START;i <= I_MAX;i++){V[I_SHIFT + i] = F[i];}
#define DF_OF_MU_FOR_TR_PO(RE_LINE_0,RE_LINE_1,RE_LINE_2,RE_LINE_3,RE_LINE_4,MU,ACCESS_ENTRY,N_OUTPUT_START,FIX_N_OUTPUT_LIM) CE CRUI 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_LINE_0;DF_0_OF__FOR_TR_PO(MU,ACCESS_ENTRY,N_OUTPUT_START);RE_LINE_1;} DF_1_OF__FOR_TR_PO(MU);RE_LINE_2;SET_N_INPUT_RANGE;FIX_N_OUTPUT_LIM;RE_LINE_3;DF_3_OF__FOR_TR_PO(MU);RE_LINE_4;
#define DF_OF_FFT_MU_FOR_TR_PO(RE_LINE_0,RE_LINE_1,RE_LINE_2,RE_LINE_3,RE_LINE_4,RE_LINE_5,MU,ACCESS_ENTRY,N_OUTPUT_START,N_OUTPUT_START_SHIFTED,FIX_N_OUTPUT_LIM,DC_OF_F0,N_INPUT_START_0,N_INPUT_LIM_0,DC_OF_F1,N_INPUT_START_1,N_INPUT_LIM_1,VE_FOR_IFFT,RESZ_VE_FOR_IFFT,I_START,MU_FORMULA,SET_AN) CE CRUI 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_LINE_0;DF_0_OF__FOR_TR_PO(MU,ACCESS_ENTRY,N_OUTPUT_START);RE_LINE_1;} DF_1_OF__FOR_TR_PO(MU);RE_LINE_2;SET_N_INPUT_RANGE;FIX_N_OUTPUT_LIM;RE_LINE_3;CO UI N_input_TR_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1;CE CRUI border_1 = FFT_MU_border_1<T>;if(N_input_TR_deg_0_deg_1 < border_1){DF_3_OF__FOR_TR_PO(MU);RE_LINE_4;} UI two_PW = FFT_MU_border_1_2<T>;UI EX = FFT_MU_border_1_2_EX<T>;T two_PW_inv{FFT_MU_border_1_2_inv<T>};WH(N_input_TR_deg_0_deg_1 >= two_PW){two_PW *= 2;two_PW_inv /= 2;EX++;} CO UI product_LE = N_input_start_0_start_1 + two_PW;DC_OF_F0;FFT<T>(f0,N_INPUT_START_0,N_INPUT_LIM_0,two_PW,EX);DC_OF_F1;FFT<T>(f1,N_INPUT_START_1,N_INPUT_LIM_1,two_PW,EX);RESZ_VE_FOR_IFFT;for(UI i = I_START + two_PW - 1;true;i--){MU_FORMULA;if(i == I_START){break;}} CO UI N_output_start_shifted = N_OUTPUT_START_SHIFTED;CO UI N_output_lim_shifted = N_output_lim_fixed - N_input_start_0_start_1;IFFT<T>(VE_FOR_IFFT,N_input_start_0_start_1,product_LE,N_output_start_shifted,N_output_lim_shifted,two_PW,two_PW_inv,EX);SET_AN;RE_LINE_5;
#define DF_OF_INVERSE_FOR_TR_PO(TYPE,RECURSION) CRUI N = f.GetTruncation();UI PW;UI PW_2 = 1;TRPO< TYPE > f_inv{PW_2,PO< TYPE >::CO_one() / f[0]};WH(PW_2 < N){PW = PW_2;PW_2 *= 2;f_inv.SetTruncation(PW_2);RECURSION;} f_inv.SetTruncation(N);RE f_inv
#define DF_OF_EXP_FOR_TR_PO(TYPE,RECURSION) CRUI N = f.GetTruncation();UI PW;UI PW_2 = 1;TRPO< TYPE > f_exp{PW_2,PO< TYPE >::CO_one()};WH(PW_2 < N){PW = PW_2;PW_2 *= 2;f_exp.SetTruncation(PW_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_EX,BORDER_1_2_INV) TE <> CE CO UI FFT_MU_border_0< TYPE > = BORDER_0;TE <> CE CO UI FFT_MU_border_1< TYPE > = BORDER_1;TE <> CE CO UI FFT_MU_border_1_2< TYPE > = BORDER_1_2;TE <> CE CO UI FFT_MU_border_1_2_EX< TYPE > = BORDER_1_2_EX;TE <> CE CO UI 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 <> IN TRPO< TYPE >& TRPO< TYPE >::OP*=(PO< TYPE >&& f) {RE TRPO< TYPE >::FFT_MU(MO(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,PW,PW_2).FFT_TRMU(f_inv,PW,PW_2),PW,PW_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),PW - 1,PW_2),PW).TRMinus(f,PW,PW_2)).FFT_TRMU(f_exp,PW,PW_2),PW,PW_2));}
TE <TY T> CL TRPO;TE <TY T> TRPO<T> Differential(CRUI n,CO TRPO<T>& f);TE <TY T> TRPO<T> TRDifferential(CO TRPO<T>& f,CRUI N_output_start_plus_one);TE <TY T> TRPO<T> TRIntegral(CO TRPO<T>& f,CRUI N_output_start);TE <TY T>CL TRPO :PU PO<T>{friend TRPO<T> Differential<T>(CRUI n,CO TRPO<T>& f);friend TRPO<T> TRDifferential<T>(CO TRPO<T>& f,CRUI N_output_start_plus_one);friend TRPO<T> TRIntegral<T>(CO TRPO<T>& f,CRUI N_output_start);PR:UI m_N;PU:IN TRPO(CRUI N = 0);IN TRPO(CO TRPO<T>& f);IN TRPO(TRPO<T>&& f);IN TRPO(CRUI N,CO T& t);IN TRPO(CRUI N,CO PO<T>& f);IN TRPO(CRUI N,PO<T>&& f);IN TRPO(CRUI N,CRUI i,CO T& t);IN TRPO(CRUI 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,CRUI N_input_start,CRUI 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,CRUI N_input_start,CRUI N_input_limit);IN TRPO<T>& OP*=(CO T& t);TRPO<T>& OP*=(CO PO<T>& f);IN TRPO<T>& OP*=(PO<T>&& f);TRPO<T>& FFT_MU(CO PO<T>& f);TRPO<T>& FFT_MU(PO<T>&& f);TRPO<T>& TRMU(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim);TRPO<T>& FFT_TRMU(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim);TRPO<T>& FFT_TRMU(PO<T>&& f,CRUI N_output_start,CRUI N_output_lim);TRPO<T> TRMU_CO(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim) CO;TRPO<T> FFT_TRMU_CO(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim) CO;TRPO<T> FFT_TRMU_CO(PO<T>&& f,CRUI N_output_start,CRUI 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 VO SetTruncation(CRUI N);IN CRUI GetTruncation() CO;IN TRPO<T>& TruncateInitial(CRUI N);IN TRPO<T>& TruncateFinal(CRUI N);};TE <TY T> IN CE CO UI FFT_MU_border_0{};TE <TY T> IN CE CO UI FFT_MU_border_1{};TE <TY T> IN CE CO UI FFT_MU_border_1_2{};TE <TY T> IN CE CO UI FFT_MU_border_1_2_EX{};TE <TY T> IN CE CO UI 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(CRUI n,CO TRPO<T>& f);TE <TY T> TRPO<T> TRDifferential(CO TRPO<T>& f,CRUI 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,CRUI 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> PW(CO TRPO<T>& f,CO T& t);TE <TY T> IN TRPO<T>::TRPO(CRUI N):PO<T>(),m_N(N) {PO<T>::m_f.reserve(m_N);}TE <TY T> IN TRPO<T>::TRPO(CO TRPO<T>& f):PO<T>(f),m_N(f.m_N) {PO<T>::m_f.reserve(m_N);}TE <TY T> IN TRPO<T>::TRPO(TRPO<T>&& f):PO<T>(MO(f)),m_N(MO(f.m_N)) {PO<T>::m_f.reserve(m_N);}TE <TY T> IN TRPO<T>::TRPO(CRUI N,CO T& t):PO<T>(t),m_N(N) {PO<T>::m_f.reserve(m_N);}TE <TY T> IN TRPO<T>::TRPO(CRUI N,CO PO<T>& f):PO<T>(),m_N(N) {PO<T>::m_SZ = f.PO<T>::m_SZ < m_N ? f.PO<T>::m_SZ:m_N;PO<T>::m_f = VE<T>(PO<T>::m_SZ);for(UI i = 0;i < PO<T>::m_SZ;i++){PO<T>::m_f[i] = f.PO<T>::m_f[i];} PO<T>::m_f.reserve(m_N);}TE <TY T> IN TRPO<T>::TRPO(CRUI N,PO<T>&& f):PO<T>(),m_N(N) {if(f.PO<T>::m_SZ < m_N * 2){PO<T>::OP=(MO(f));if(f.PO<T>::m_SZ < m_N){PO<T>::m_f.reserve(m_N);} else {TruncateFinal(m_N);}} else {PO<T>::m_f = VE<T>(m_N);for(UI i = 0;i < m_N;i++){PO<T>::m_f[i] = MO(f.PO<T>::m_f[i]);} PO<T>::m_SZ = m_N;}}TE <TY T> IN TRPO<T>::TRPO(CRUI N,CRUI i,CO T& t):PO<T>(),m_N(N) {if(i < m_N ? t != PO<T>::CO_zero():false){PO<T>::OP[](i) = t;} PO<T>::m_f.reserve(m_N);}TE <TY T> IN TRPO<T>::TRPO(CRUI N,VE<T>&& f):PO<T>(),m_N(N) {CO UI f_SZ = f.SZ();if(f_SZ < m_N * 2){PO<T>::OP=(MO(f));if(f_SZ < m_N){PO<T>::m_f.reserve(m_N);} else {TruncateFinal(m_N);}} else {PO<T>::m_f = VE<T>(m_N);for(UI i = 0;i < m_N;i++){PO<T>::m_f[i] = MO(f[i]);} PO<T>::m_f.reserve(m_N);}}TE <TY T> IN TRPO<T>& TRPO<T>::OP=(CO TRPO<T>& f) {PO<T>::OP=(f);m_N = f.m_N;PO<T>::m_f.reserve(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);PO<T>::m_f.reserve(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.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,CRUI N_input_start,CRUI N_input_lim){CRUI SZ = N_input_lim < m_N ? N_input_lim < f.PO<T>::m_SZ ? N_input_lim:f.PO<T>::m_SZ:m_N < f.PO<T>::m_SZ ? m_N:f.PO<T>::m_SZ;if(PO<T>::m_SZ < SZ){PO<T>::m_f.reserve(SZ);for(UI i = N_input_start;i < PO<T>::m_SZ;i++){PO<T>::m_f[i] += f.PO<T>::m_f[i];}for(UI i = PO<T>::m_SZ;i < SZ;i++){PO<T>::m_f.push_back(f.PO<T>::m_f[i]);}PO<T>::m_SZ = SZ;} else {for(UI i = N_input_start;i < SZ;i++){PO<T>::m_f[i] += f.PO<T>::m_f[i];}}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.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,CRUI N_input_start,CRUI N_input_lim){CRUI SZ = N_input_lim < m_N ? N_input_lim < f.PO<T>::m_SZ ? N_input_lim:f.PO<T>::m_SZ:m_N < f.PO<T>::m_SZ ? m_N:f.PO<T>::m_SZ;if(PO<T>::m_SZ < SZ){PO<T>::m_f.reserve(SZ);for(UI i = N_input_start;i < PO<T>::m_SZ;i++){PO<T>::m_f[i] -= f.PO<T>::m_f[i];}for(UI i = PO<T>::m_SZ;i < SZ;i++){PO<T>::m_f.push_back(- f.PO<T>::m_f[i]);}PO<T>::m_SZ = SZ;} else {for(UI i = N_input_start;i < SZ;i++){PO<T>::m_f[i] -= f.PO<T>::m_f[i];}}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(MP,17,512,1024,10,997269505);TE <TY T>TRPO<T>& TRPO<T>::OP*=(CO PO<T>& f){DF_OF_MU_FOR_TR_PO(RE_ZERO_FOR_MU_FOR_TR_PO_IF(f.PO<T>::m_SZ == 0),, RE_ZERO_FOR_MU_FOR_TR_PO_IF(searching),RE_ZERO_FOR_MU_FOR_TR_PO_IF(N_input_start_0_start_1 >= m_N),RE *this,MU,PO<T>::m_f,0 ,);}TE <TY T> IN TRPO<T>& TRPO<T>::OP*=(PO<T>&& f){RE OP*=(f);}TE <TY T>TRPO<T>& TRPO<T>::FFT_MU(CO PO<T>& f){DF_OF_FFT_MU_FOR_TR_PO(RE_ZERO_FOR_MU_FOR_TR_PO_IF(f.PO<T>::m_SZ == 0),RE *this,RE_ZERO_FOR_MU_FOR_TR_PO_IF(searching),RE_ZERO_FOR_MU_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE *this,RE *this,MU,PO<T>::m_f[j],0,0,, VE<T>& f0 = PO<T>::m_f,N_input_start_0,N_input_max_0 + 1,SET_SHIFTED_VE_FOR_MU(f1,f.PO<T>::m_f,N_input_start_1,N_input_max_1,N_input_start_0),N_input_start_0_start_1,N_input_start_0 + N_input_max_1 + 1,f1,, N_input_start_0,f1[N_input_start_1 + i] *= f0[i],OP=(TRPO<T>(m_N,MO(f1))));}TE <TY T>TRPO<T>& TRPO<T>::FFT_MU(PO<T>&& f){DF_OF_FFT_MU_FOR_TR_PO(RE_ZERO_FOR_MU_FOR_TR_PO_IF(f.PO<T>::m_SZ == 0),RE *this,RE_ZERO_FOR_MU_FOR_TR_PO_IF(searching),RE_ZERO_FOR_MU_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE *this,RE *this,MU,PO<T>::m_f[j],0,0,, VE<T>& f0 = PO<T>::m_f,N_input_start_0,N_input_max_0 + 1,VE<T>&& f1 = MO(f.PO<T>::m_f),N_input_start_1,N_input_max_1 + 1,f0,f0.resize(product_LE),0,f0[N_input_start_0_start_1 + i] = f0[N_input_start_0 + i] * f1[N_input_start_1 + i],for(UI i = N_input_start_0;i < N_input_start_0_start_1;i++){f0[i] = 0;} PO<T>::m_SZ = f0.SZ();SetTruncation(m_N););}TE <TY T> TRPO<T>& TRPO<T>::TRMU(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim){DF_OF_MU_FOR_TR_PO(, RE *this,, RE_ZERO_FOR_MU_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE *this,MU,PO<T>::m_f[j],N_output_start,if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;});}TE <TY T> TRPO<T>& TRPO<T>::FFT_TRMU(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim){DF_OF_FFT_MU_FOR_TR_PO(, RE *this,, RE_ZERO_FOR_MU_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE *this,RE *this,MU,PO<T>::m_f[j],N_output_start,N_output_start < N_input_start_0_start_1 ? 0:N_output_start - N_input_start_0_start_1,if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;},VE<T>& f0 = PO<T>::m_f,N_input_start_0,N_input_max_0 + 1,SET_SHIFTED_VE_FOR_MU(f1,f.PO<T>::m_f,N_input_start_0,N_input_max_1,N_input_start_1),N_input_start_0_start_1,N_input_start_0 + N_input_max_1 + 1,f1,, N_input_start_0,f1[N_input_start_1 + i] *= f0[i],OP=(TRPO<T>(m_N,MO(f1))));}TE <TY T> TRPO<T>& TRPO<T>::FFT_TRMU(PO<T>&& f,CRUI N_output_start,CRUI N_output_lim){DF_OF_FFT_MU_FOR_TR_PO(, RE *this,, RE_ZERO_FOR_MU_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE *this,RE *this,MU,PO<T>::m_f,N_output_start,N_output_start < N_input_start_0_start_1 ? 0:N_output_start - N_input_start_0_start_1,if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;},VE<T>& f0 = PO<T>::m_f,N_input_start_0,N_input_max_0 + 1,VE<T>&& f1 = MO(f.PO<T>::m_f),N_input_start_1,N_input_max_1 + 1,f0,f0.reserve(product_LE),0,f1[N_input_start_0_start_1 + i] = f0[N_input_start_0 + i] * f1[N_input_start_1 + i],for(UI i = N_input_start_0;i < N_input_start_0_start_1;i++){f0[i] = 0;} PO<T>::m_SZ = f0.SZ();SetTruncation(m_N););}TE <TY T> TRPO<T> TRPO<T>::TRMU_CO(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim) CO{DF_OF_MU_FOR_TR_PO(, RE TRPO<T>(m_N,MO(AN)),, RE_ZERO_FOR_TR_MU_CO_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE TRPO<T>(m_N,MO(AN)),TR_MU_CO,PO<T>::OP[](j),N_output_start,if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;});}TE <TY T> TRPO<T> TRPO<T>::FFT_TRMU_CO(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim) CO{DF_OF_FFT_MU_FOR_TR_PO(, RE TRPO<T>(m_N,MO(AN)),, RE_ZERO_FOR_TR_MU_CO_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE TRPO<T>(m_N,MO(AN)),RE TRPO<T>(m_N,MO(f0)),TR_MU_CO,PO<T>::OP[](j),N_output_start,N_output_start < N_input_start_0_start_1 ? 0:N_output_start - N_input_start_0_start_1,if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;},SET_SHIFTED_VE_FOR_MU(f0,PO<T>::m_f,N_input_start_0,N_input_max_0,N_input_start_1),N_input_start_0_start_1,N_input_start_1 + N_input_max_0 + 1,VE<T> f1 = f.PO<T>::m_f,N_input_start_1,N_input_max_1 + 1,f0,, N_input_start_1,f0[N_input_start_0 + i] *= f1[i] ,);}TE <TY T> TRPO<T> TRPO<T>::FFT_TRMU_CO(PO<T>&& f,CRUI N_output_start,CRUI N_output_lim) CO{DF_OF_FFT_MU_FOR_TR_PO(, RE TRPO<T>(m_N,MO(AN)),, RE_ZERO_FOR_TR_MU_CO_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE TRPO<T>(m_N,MO(AN)),RE TRPO<T>(m_N,MO(f0)),TR_MU_CO,PO<T>::OP[](j),N_output_start,N_output_start < N_input_start_0_start_1 ? 0:N_output_start - N_input_start_0_start_1,if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;},SET_SHIFTED_VE_FOR_MU(f0,PO<T>::m_f,N_input_start_0,N_input_max_0,N_input_start_1),N_input_start_0_start_1,N_input_start_1 + N_input_max_0 + 1,VE<T>&& f1 = MO(f.PO<T>::m_f),N_input_start_1,N_input_max_1 + 1,f0,, N_input_start_1,f0[N_input_start_0 + i] *= f1[i] ,);}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 MO(TRPO<T>(m_N) -= *this);}TE <TY T> IN VO TRPO<T>::SetTruncation(CRUI N) {if(N < m_N){TruncateFinal(m_N);} else {PO<T>::m_f.reserve(N);} m_N = N;}TE <TY T> IN CRUI TRPO<T>::GetTruncation() CO {RE m_N;}TE <TY T> IN TRPO<T>& TRPO<T>::TruncateInitial(CRUI N) {CRUI SZ = N < PO<T>::m_SZ ? N:PO<T>::m_SZ;for(UI i = 0;i < SZ;i++){PO<T>::m_f[i] = 0;} RE *this;}TE <TY T> IN TRPO<T>& TRPO<T>::TruncateFinal(CRUI N) {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 MO(TRPO<T>(f0) += f1);}TE <TY T,TY P> IN TRPO<T> OP-(CO TRPO<T>& f) {RE MO(TRPO<T>(f.GetTurncation()) -= f);}TE <TY T,TY P> IN TRPO<T> OP-(CO TRPO<T>& f0,CO P& f1) {RE MO(TRPO<T>(f0) -= f1);}TE <TY T,TY P> IN TRPO<T> OP*(CO TRPO<T>& f0,CO P& f1) {RE MO(TRPO<T>(f0) *= f1);}TE <TY T,TY P> IN TRPO<T> OP/(CO TRPO<T>& f0,CO P& f1) {RE MO(TRPO<T>(f0) /= f1);}TE <TY T> IN TRPO<T> OP%(CO TRPO<T>& f0,CO T& t1) {RE MO(TRPO<T>(f0) %= t1);}TE <TY T> IN TRPO<T> Differential(CO TRPO<T>& f) {RE TRDifferential<T>(f,1);}TE <TY T>TRPO<T> Differential(CRUI n,CO TRPO<T>& f){if(f.PO<T>::m_SZ < n){RE TRPO(f.m_N - n,PO<T>::zero());}VE<T> df(f.PO<T>::m_SZ - n);T coef = PO<T>::factorial(n);UI i = n;WH(i < f.PO<T>::m_SZ){df[i - n] = f[i] * coef;i++;(coef *= i) /= (i - n);}RE TRPO(f.m_N - n,MO(df));}TE <TY T>TRPO<T> TRDifferential(CO TRPO<T>& f,CRUI N_output_start_plus_one){assert(f.m_N > 0);TRPO<T> f_dif{f.m_N - 1};if(N_output_start_plus_one < f.PO<T>::m_SZ){CO UI SZ = f.PO<T>::m_SZ - 1;f_dif.PO<T>::m_f = VE<T>(SZ);for(UI i = N_output_start_plus_one;i < f.PO<T>::m_SZ;i++){f_dif.PO<T>::m_f[i-1] = i * f.PO<T>::m_f[i];}f_dif.PO<T>::m_SZ = SZ;}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,CRUI N_output_start){TRPO<T> f_int{f.m_N + 1};if(N_output_start <= f.PO<T>::m_SZ){CO UI SZ = f.PO<T>::m_SZ + 1;f_int.PO<T>::m_f = VE<T>(SZ);for(UI i = N_output_start;i <= f.PO<T>::m_SZ;i++){f_int.PO<T>::m_f[i] = f.PO<T>::m_f[i - 1] / T(i);}f_int.PO<T>::m_SZ = SZ;}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,PW,PW_2).TRMU(f_inv,PW,PW_2),PW,PW_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),PW - 1,PW_2),PW).TRMinus(f,PW,PW_2)).TRMU(f_exp,PW),PW,PW_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> PW(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(CRUI 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 = MO(f.m_f);m_SZ = MO(f.m_SZ);RE *this;}TE <TY T>CO T& PO<T>::OP[](CRUI i) CO{if(m_SZ <= i){RE CO_zero();}RE m_f[i];}TE <TY T> IN T& PO<T>::OP[](CRUI 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 MO((*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(UI 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(UI i = 0;i < f.m_SZ;i++){OP[](i) -= f.m_f[i];}RE *this;}DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(MP);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(UI i = 0;i < m_SZ;i++){m_f[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){m_f.clear();m_SZ = 0;RE *this;}CO UI SZ = m_SZ + f.m_SZ - 1;PO<T> product{};for(UI i = 0;i < SZ;i++){T& product_i = product[i];CO UI j_min = m_SZ <= i ? i - m_SZ + 1:0;CO UI j_lim = i < f.m_SZ ? i + 1:f.m_SZ;for(UI j = j_min;j < j_lim;j++){product_i += m_f[i - j] * f.m_f[j];}}RE OP=(MO(product));}TE <TY T> IN PO<T>& PO<T>::OP*=(PO<T>&& f) {RE OP*=(f);};TE <TY T>PO<T>& PO<T>::OP/=(CO T& t){if(t == CO_one()){RE *this;}CO T t_inv{CO_one() / t};for(UI i = 0;i < m_SZ;i++){OP[](i) *= t_inv;}RE *this;}TE <TY T> IN PO<T>& PO<T>::OP/=(CO PO<T>& f) {RE m_SZ < f.m_SZ ? *this:OP=(Quotient(*this,f));}TE <TY T>PO<T> PO<T>::Quotient(CO PO<T>& f0,CO PO<T>& f1){if(f0.m_SZ < f1.m_SZ){RE f0;}assert(f1.m_SZ > 0);CO UI f0_transpose_SZ = f0.m_SZ - f1.m_SZ + 1;CO UI f1_transpose_SZ = f0_transpose_SZ < f1.m_SZ ? f0_transpose_SZ:f1.m_SZ;RE TransposeQuotient(f0,f0_transpose_SZ,Inverse(TRPO<T>(f0_transpose_SZ,Transpose(f1,f1_transpose_SZ))),f1.m_SZ);}TE <TY T>PO<T> PO<T>::TransposeQuotient(CO PO<T>& f0,CRUI f0_transpose_SZ,CO PO<T>& f1_transpose_inverse,CRUI f1_SZ){TRPO<T> f0_transpose{f0_transpose_SZ,Transpose(f0,f0_transpose_SZ)};f0_transpose *= f1_transpose_inverse;for(UI d0 = (f0_transpose_SZ + 1) / 2;d0 < f0_transpose_SZ;d0++){::swap(f0_transpose.PO<T>::m_f[d0],f0_transpose.PO<T>::m_f[ f0_transpose_SZ - 1 - d0 ]);}RE f0_transpose;}TE <TY T>PO<T> PO<T>::Transpose(CO PO<T>& f,CRUI f_transpose_SZ){VE<T> f_transpose(f_transpose_SZ);for(UI d = 0;d < f_transpose_SZ;d++){f_transpose[d] = f.m_f[f.m_SZ - 1 - d];}RE PO<T>(MO(f_transpose));}TE <TY T>PO<T>& PO<T>::OP%=(CO T& t){if(t == CO_one()){RE OP=(zero());}for(UI i = 0;i < m_SZ;i++){m_f[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 MO(PO<T>() -= *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};UI SZ = factorial.SZ();WH(SZ < m_SZ){factorial.push_back(factorial_curr *= SZ);factorial_inv.push_back(factorial_inv_curr /= SZ);SZ++;}for(UI d = 0;d < m_SZ;d++){m_f[d] *= factorial[d];}TRPO<T> exp_t_transpose{m_SZ * 2};T PW_t = CO_one();for(UI d = 0;d < m_SZ;d++){exp_t_transpose[m_SZ - 1 - d] = PW_t * factorial_inv[d];PW_t *= t;}exp_t_transpose *= *this;for(UI d = 0;d < m_SZ;d++){m_f[d] = exp_t_transpose.PO<T>::m_f[d + m_SZ - 1] * factorial_inv[d];}}RE *this;}TE <TY T> IN CO VE<T>& PO<T>::GetCoefficient() CO {RE m_f;}TE <TY T> IN CRUI PO<T>::SZ() CO {RE m_SZ;}TE <TY T> IN VO PO<T>::swap(PO<T>& f) {m_f.swap(f.m_f);swap(m_SZ,f.m_SZ);}TE <TY T> IN VO PO<T>::swap(VE<T>& f) {m_f.swap(f);m_SZ = m_f.SZ();}TE <TY T>VO 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{string s = "(";if(m_SZ > 0){s += to_string(m_f[0]);for(UI 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(CRUI i) {ST VE<T> memory = {CO_one(),CO_one()};ST T curr = CO_one();ST UI SZ = 2;WH(SZ <= i){memory.push_back(curr *= SZ++);} RE memory[i];}TE <TY T> IN CO T& PO<T>::factorial_inverse(CRUI i) {ST VE<T> memory = {CO_one(),CO_one()};ST T curr = CO_one();ST UI 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){CRUI SZ = f0.SZ();CO T& zero = PO<T>::CO_zero();for(UI 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){CRUI SZ0 = f0.SZ();CRUI SZ1 = f1.SZ();CRUI SZ = SZ0 < SZ1 ? SZ1:SZ0;for(UI i = 0;i < SZ;i++){if(f0[i] != f1[i]){RE false;}}RE true;}TE <TY T,TY P> IN bool OP!=(CO PO<T>& f0,CO P& f1) {RE !(f0 == f1);}TE <TY T,TY P> IN PO<T> OP+(CO PO<T>& f0,CO P& f1) {RE MO(PO<T>(f0) += f1);}TE <TY T,TY P> IN PO<T> OP-(CO PO<T>& f) {RE PO<T>::zero() - f;}TE <TY T,TY P> IN PO<T> OP-(CO PO<T>& f0,CO P& f1) {RE MO(PO<T>(f0) -= f1);}TE <TY T,TY P> IN PO<T> OP*(CO PO<T>& f0,CO P& f1) {RE MO(PO<T>(f0) *= f1);}TE <TY T> IN PO<T> OP/(CO PO<T>& f0,CO T& t1) {RE MO(PO<T>(f0) /= t1);}TE <TY T> IN PO<T> OP/(CO PO<T>& f0,CO PO<T>& f1) {RE PO<T>::Quotient(f0,f1);}TE <TY T,TY P> IN PO<T> OP%(CO PO<T>& f0,CO P& f1) {RE MO(PO<T>(f0) %= f1);}TE <TY T> PO<T> OP<<(CO PO<T>& f,CO T& t) {RE MO(PO<T>(f) <<= t);};TE <TY T,TE <TY> TY V>T& Prod(V<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 *= *I;I = f.erase(I);}}RE Prod(f);}
TE <TY T,TE <TY> TY V1,TE <TY> TY V2,TE <TY> TY V3>VO SetPointTreeEvaluation(CO PO<T>& f,CO V1<V2<PO<T> > >& point_tree,V3<T>& AN){CO V2<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,TE <TY> TY V1,TE <TY> TY V2> IN VO SetMultipointEvaluation(CO PO<T>& f,CO V1<T>& point,V2<T>& AN) {LI<LI<PO<T> > > pt{};SetPointTree(point,pt);SetPointTreeEvaluation(f,pt,AN);}TE <TY T,TE <TY> TY V1,TE <TY> TY V2 >VO SetProductTree(V1<V2<T> >& product_tree){V2<T> empty{};V2<T> *p_node = &(product_tree.back());WH(p_node->SZ() > 1){product_tree.push_front(empty);V2<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,TE <TY> TY V1,TE <TY> TY V2,TE <TY> TY V3>VO SetPointTree(CO V1<T>& point,V2<V3<PO<T> > >& point_tree){ST CO V3<PO<T> > empty{};point_tree.push_front(empty);V3<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>US TT = VE<VE<T> >;TE <UI Y,UI X,TY T>CL MA{PR:TT<T> m_M;PU:IN MA(CO T& t = T());IN MA(CRI t);TE <TY... Args> IN MA(CO T& t0,CO T& t1,CO Args&... args);TE <TY... Args> IN MA(T&& t0,T&& t1,Args&&... args);IN MA(CO MA<Y,X,T>& mat);IN MA(MA<Y,X,T>&& mat);TE <TY... Args> IN MA(CO TT<T>& M);TE <TY... Args> IN MA(TT<T>&& M);IN MA<Y,X,T>& operator=(CO MA<Y,X,T>& mat);IN MA<Y,X,T>& operator=(MA<Y,X,T>&& mat);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);IN MA<Y,X,T>& operator*=(CO MA<X,X,T>& mat);MA<Y,X,T>& operator%=(CO T& scalar);IN TT<T>& RefTable();IN CO TT<T>& GetTable() CO;ST IN CO MA<Y,X,T>& Zero();ST IN CO MA<Y,X,T>& Unit();ST MA<Y,X,T> Scalar(CO T& t);PR:ST IN VO COructTable(TT<T>& M,VE<T>& vec);TE <TY... Args> ST VO COructTable(TT<T>& M,VE<T>& vec,CO T& t,CO Args&... args);TE <TY... Args> ST VO COructTable(TT<T>& M,VE<T>& vec,T&& t,Args&&... args);ST MA<Y,X,T> Zero_Body();};TE <UI Y,UI X,TY T> IN MA<Y,X,T> operator==(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2);TE <UI Y,UI X,TY T> IN MA<Y,X,T> operator!=(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2);TE <UI Y,UI X,TY T> IN MA<Y,X,T> operator+(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2);TE <UI Y,UI X,TY T> IN MA<Y,X,T> operator-(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2);TE <UI Y,UI X,UI Z,TY T>MA<Y,Z,T> operator*(CO MA<Y,X,T>& mat1,CO MA<X,Z,T>& mat2);TE <UI Y,UI X,TY T> IN MA<Y,X,T> operator*(CO MA<Y,X,T>& mat,CO T& scalar);TE <UI Y,UI X,TY T> IN MA<Y,X,T> operator*(CO T& scalar,CO MA<Y,X,T>& mat);TE <UI Y,UI X,TY T> IN MA<Y,X,T> operator%(CO MA<Y,X,T>& mat,CO T& scalar);TE <UI Y,UI X,TY T>MA<X,Y,T> Transpose(CO MA<Y,X,T>& mat);TE <UI X,TY T>T Trace(CO MA<X,X,T>& mat);TE <UI Y,UI X,TY T> IN MA<Y,X,T>::MA(CO T& t):m_M() {operator=(MO(Scalar(t)));}TE <UI Y,UI X,TY T> IN MA<Y,X,T>::MA(CRI t):MA(T(t)) {}TE <UI Y,UI X,TY T> TE <TY... Args>MA<Y,X,T>::MA(CO T& t0,CO T& t1,CO Args&... args): m_M(){VE<T> vec{};COructTable(m_M,vec,t0,t1,args...);}TE <UI Y,UI X,TY T> TE <TY... Args>MA<Y,X,T>::MA(T&& t0,T&& t1,Args&&... args): m_M(){VE<T> vec{};COructTable(m_M,vec,MO(t0),MO(t1),MO(args)...);}TE <UI Y,UI X,TY T> IN MA<Y,X,T>::MA(CO MA<Y,X,T>& mat):m_M(mat.m_M) {}TE <UI Y,UI X,TY T> IN MA<Y,X,T>::MA(MA<Y,X,T>&& mat):m_M(MO(mat.m_M)) {}TE <UI Y,UI X,TY T> TE <TY... Args> IN MA<Y,X,T>::MA(CO TT<T>& M):m_M(M) {}TE <UI Y,UI X,TY T> TE <TY... Args> IN MA<Y,X,T>::MA(TT<T>&& M):m_M(MO(M)) {}TE <UI Y,UI X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::operator=(CO MA<Y,X,T>& mat) {m_M = mat.m_M;RE *this;}TE <UI Y,UI X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::operator=(MA<Y,X,T>&& mat) {m_M = move(mat.m_M);RE *this;}TE <UI Y,UI 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 <UI Y,UI 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 <UI Y,UI X,TY T> MA<Y,X,T>& MA<Y,X,T>::operator*=(CO T& scalar){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 <UI Y,UI X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::operator*=(CO MA<X,X,T>& mat) {RE operator=(MO(*this * mat));}TE <UI Y,UI X,TY T> MA<Y,X,T>& MA<Y,X,T>::operator%=(CO T& scalar){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 <UI Y,UI X,TY T> IN TT<T>& MA<Y,X,T>::RefTable() {RE m_M;}TE <UI Y,UI X,TY T> IN CO TT<T>& MA<Y,X,T>::GetTable() CO {RE m_M;}TE <UI Y,UI X,TY T> IN CO MA<Y,X,T>& MA<Y,X,T>::Zero() {ST CO MA<Y,X,T> zero = MO(Zero_Body());RE zero;}TE <UI Y,UI X,TY T> IN CO MA<Y,X,T>& MA<Y,X,T>::Unit() {ST CO MA<Y,X,T> unit = MO(Scalar(T(1)));RE unit;}TE <UI Y,UI X,TY T>MA<Y,X,T> MA<Y,X,T>::Zero_Body(){VE<T> vec(X);TT<T> M(Y,vec);RE MA<Y,X,T>(MO(M));}TE <UI Y,UI X,TY T>MA<Y,X,T> MA<Y,X,T>::Scalar(CO T& t){MA<Y,X,T> M{MO(Zero_Body())};CE CO UI minXY = Y < X ? Y:X;for(UI y = 0;y < minXY;y++){M.m_M[y][y] = t;}RE M;}TE <UI Y,UI X,TY T> IN VO MA<Y,X,T>::COructTable(TT<T>& M,VE<T>& vec) {M.push_back(MO(vec));}TE <UI Y,UI X,TY T> TE <TY... Args> VO MA<Y,X,T>::COructTable(TT<T>& M,VE<T>& vec,CO T& t,CO Args&... args){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 <UI Y,UI X,TY T> TE <TY... Args> VO MA<Y,X,T>::COructTable(TT<T>& M,VE<T>& vec,T&& t,Args&&... args){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 <UI Y,UI X,TY T> IN MA<Y,X,T> operator==(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) {RE mat1.GetTable() == mat2.GetTable();}TE <UI Y,UI X,TY T> IN MA<Y,X,T> operator!=(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) {RE !(mat1 == mat2);}TE <UI Y,UI 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 <UI Y,UI 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 <UI Y,UI X,UI 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(UI 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 <UI Y,UI 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 <UI Y,UI X,TY T> IN MA<Y,X,T> operator*(CO T& scalar,CO MA<Y,X,T>& mat) {RE mat * scalar;}TE <UI Y,UI 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 <UI Y,UI 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 <UI 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>CL TTMA{PR:T m_M00;T m_M01;T m_M10;T m_M11;PU:IN TTMA(CO T& M00,CO T& M01,CO T& M10,CO T& M11);IN TTMA(T&& M00,T&& M01,T&& M10,T&& M11);IN TTMA(CO T& n = T());IN TTMA(CRI n);IN TTMA(CO MA<2,2,T>& mat);IN TTMA(CO TTMA<T>& mat);IN TTMA(TTMA<T>&& mat);IN TTMA<T>& OP=(CO TTMA<T>& mat);IN TTMA<T>& OP=(TTMA<T>&& mat);IN TTMA<T>& OP*=(CO TTMA<T>& mat);IN MA<2,2,T> GetMA22() CO;ST IN TTMA<T> Multiply(CO TTMA<T>& mat1,CO TTMA<T>& mat2);ST IN TTMA<T> Square(CO TTMA<T>& mat);};TE <TY T> IN TTMA<T>::TTMA(CO T& M00,CO T& M01,CO T& M10,CO T& M11):m_M00(M00),m_M01(M01),m_M10(M10),m_M11(M11) {}TE <TY T> IN TTMA<T>::TTMA(T&& M00,T&& M01,T&& M10,T&& M11):m_M00(MO(M00)),m_M01(MO(M01)),m_M10(MO(M10)),m_M11(MO(M11)) {}TE <TY T> IN TTMA<T>::TTMA(CO T& n):m_M00(n),m_M01(),m_M10(),m_M11(n) {}TE <TY T> IN TTMA<T>::TTMA(CRI n):TTMA(T(n)) {}TE <TY T> IN TTMA<T>::TTMA(CO TTMA<T>& mat):m_M00(mat.m_M00),m_M01(mat.m_M01),m_M10(mat.m_M10),m_M11(mat.m_M11) {}TE <TY T> IN TTMA<T>::TTMA(TTMA<T>&& mat):m_M00(MO(mat.m_M00)),m_M01(MO(mat.m_M01)),m_M10(MO(mat.m_M10)),m_M11(MO(mat.m_M11)) {}TE <TY T>TTMA<T>::TTMA(CO MA<2,2,T>& mat): m_M00(),m_M01(),m_M10(),m_M11(){CO TT<T>& M = mat.GetTable();CO VE<T>& M0 = M[0];CO VE<T>& M1 = M[1];m_M00 = M0[0];m_M01 = M0[1];m_M10 = M1[0];m_M11 = M1[1];}TE <TY T> IN TTMA<T>& TTMA<T>::OP=(CO TTMA<T>& mat) {if(&mat != this){m_M00 = mat.m_M00;m_M01 = mat.m_M01;m_M10 = mat.m_M10;m_M11 = mat.m_M11;} RE *this;}TE <TY T> IN TTMA<T>& TTMA<T>::OP=(TTMA<T>&& mat) {m_M00 = MO(mat.m_M00);m_M01 = MO(mat.m_M01);m_M10 = MO(mat.m_M10);m_M11 = MO(mat.m_M11);RE *this;}TE <TY T> IN TTMA<T>& TTMA<T>::OP*=(CO TTMA<T>& mat) {RE OP=(Multiply(*this,mat));}TE <TY T> IN MA<2,2,T> TTMA<T>::GetMA22() CO {RE MA<2,2,T>(m_M00,m_M01,m_M10,m_M11);}TE <TY T> IN TTMA<T> TTMA<T>::Multiply(CO TTMA<T>& mat1,CO TTMA<T>& mat2) {RE TTMA<T>(mat1.m_M00 * mat2.m_M00 + mat1.m_M01 * mat2.m_M10,mat1.m_M00 * mat2.m_M01 + mat1.m_M01 * mat2.m_M11,mat1.m_M10 * mat2.m_M00 + mat1.m_M11 * mat2.m_M10,mat1.m_M10 * mat2.m_M01 + mat1.m_M11 * mat2.m_M11);}TE <TY T> IN TTMA<T> TTMA<T>::Square(CO TTMA<T>& mat) {RE TTMA<T>(mat.m_M00 * mat.m_M00 + mat.m_M01 * mat.m_M10,(mat.m_M00 + mat.m_M11) * mat.m_M01,mat.m_M10 * (mat.m_M00 + mat.m_M11),mat.m_M10 * mat.m_M01 + mat.m_M11 * mat.m_M11);}TE <TY T> IN TTMA<T> OP*(CO TTMA<T>& mat1,CO TTMA<T>& mat2) {RE TTMA<T>::Multiply(mat1,mat2);}TE <TY T> IN TTMA<T> Square(CO TTMA<T>& mat) {RE TTMA<T>::Square(mat);}
#define SET_MA_MULTIPOINT_EVALUATION(SAMPLE_NUM_MAX,FINAL_LENGTH,POINT) point = VE<T>(SAMPLE_NUM_MAX + 1);for(UI t = 0;t <= SAMPLE_NUM_MAX;t++){point[t] = POINT;} LI<LI<PO<T> > > pt{};SetPointTree(point,pt);VE<T> eval[Y][Y] = {};for(UI y = 0;y < Y;y++){CO VE<PO<T> >& M_ref_y = M_ref[y];VE<T> (&eval_y)[Y] = eval[y];for(UI x = 0;x < Y;x++){SetPointTreeEvaluation(M_ref_y[x],pt,eval_y[x]);}} VE<MA<Y,Y,T> > sample(SAMPLE_NUM_MAX + 1,MA<Y,Y,T>::Zero());sample.reserve(FINAL_LENGTH);for(UI t = 0;t <= SAMPLE_NUM_MAX;t++){VE<VE<T> >& sample_t_ref = sample[t].RefTable();for(UI y = 0;y < Y;y++){VE<T>& sample_t_ref_y = sample_t_ref[y];VE<T> (&eval_y)[Y] = eval[y];for(UI 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(UI t = 0;t <= subinterval_num_max;t++){sample[t] = eval_odd[t] * sample[t];} for(UI t = 0;t < REST_INTERVAL_LENGTH;t++){sample.push_back(eval_odd[t + subinterval_num_max + 1] * eval_even[t]);}
TE <TY T>VO SetIntervalEvaluation(CRUI deg,CO T& t_start,CRUI length,VE<T>& eval);TE <UI Y,UI X,TY T>VO SetIntervalEvaluation(CRUI deg,CO T& t_start,CRUI length,CO VE<MA<Y,X,T> >& sample,VE<MA<Y,X,T> >& eval);TE <UI Y,TY T>VO SetPRecursiveMAAction(CO MA<Y,Y,PO<T> >& M,MA<Y,1,T>& v,CRUI length);TE <TY T>VO SetIntervalEvaluation(CRUI deg,CO T& t_start,CRUI length,VE<T>& eval){for(UI 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(UI 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();UI deg_f = f.SZ();if(deg_f == 0){eval = VE<T>(length,PO<T>::CO_zero());RE;} f.SetTruncation(deg_f);deg_f--;for(UI d = 0;d <= deg_f;d++){f[d] *= PO<T>::factorial(d);} UI deg_f_half = (deg_f + 1) / 2;for(UI 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(UI 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(UI d = 0;d < deg_f_half;d++){swap(f[d],f[deg_f - d]);} for(UI d = 0;d <= deg_f;d++){f[d] *= PO<T>::factorial_inverse(d);} f.SetTruncation(length);ST PO<T> exp{};for(UI d = exp.SZ();d < length;d++){exp[d] = PO<T>::factorial_inverse(d);} f *= exp;for(UI d = 0;d < length;d++){f[d] *= PO<T>::factorial(d);} f.swap(eval);RE;}TE <UI Y,UI X,TY T>VO SetIntervalEvaluation(CRUI deg,CO T& t_start,CRUI 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(UI t = 0;t <= deg;t++){CO VE<VE<T> >& table = sample[t].GetTable();for(UI y = 0;y < Y;y++){VE<T> (&sample_copy_y)[X] = sample_copy[y];CO VE<T>& table_y = table[y];for(UI x = 0;x < X;x++){sample_copy_y[x].push_back(table_y[x]);}}} for(UI y = 0;y < Y;y++){VE<T> (&sample_copy_y)[X] = sample_copy[y];for(UI x = 0;x < X;x++){VE<T>& sample_copy_yx = sample_copy_y[x];SetIntervalEvaluation(deg,t_start,length,sample_copy_yx);for(UI i = 0;i < length;i++){VE<VE<T> >& table = eval[i].RefTable();table[y][x] = sample_copy_yx[i];}}} RE;}TE <UI Y,TY T>VO SetPRecursiveMAAction(CO MA<Y,Y,PO<T> >& M,MA<Y,1,T>& v,CRUI length){if(length == 0){RE;} CO VE<VE<PO<T> > >& M_ref = M.GetTable();UI deg = 1;for(UI y = 0;y < Y;y++){CO VE<PO<T>>& M_ref_y = M_ref[y];for(UI x = 0;x < Y;x++){CRUI SZ = M_ref_y[x].SZ();if(deg < SZ){deg = SZ;}}} deg--;UI interval_length = 1;int exponent = 0;WH(interval_length * (interval_length * deg + 1) <= length){interval_length *= 2;exponent++;} interval_length /= 2;exponent--;UI interval_num_max;UI t_rest_start;VE<T> point{};if(exponent > 0){CO UI interval_num_lim = length / interval_length;interval_num_max = interval_num_lim - 1;t_rest_start = interval_length * interval_num_lim;UI subinterval_num_max = deg;T subinterval_length = PO<T>::CO_one();SET_MA_MULTIPOINT_EVALUATION(subinterval_num_max,interval_num_lim,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;} UI rest_interval_length = interval_num_max - subinterval_num_max;MULTIPLY_SUBPRODUCT_OF_PRECURSIVE_MA(rest_interval_length);for(UI t = 0;t <= interval_num_max;t++){v = sample[t] * v;}} else {interval_num_max = t_rest_start = 0;} if(t_rest_start < length){CO UI rest_num_lim = length - t_rest_start;CO UI rest_num_max = rest_num_lim - 1;SET_MA_MULTIPOINT_EVALUATION(rest_num_max,rest_num_lim,t + t_rest_start);for(UI t = 0;t <= rest_num_max;t++){v = sample[t] * v;}} RE;}
CL Query{PU:ll m_N;ll m_K;int m_t;IN Query(const ll& N = 0,const ll& K = 0,int t = 0) : m_N(N),m_K(K),m_t(t) {}};IN bool operator<(const Query& q1,const Query& q2) {return q1.m_K < q2.m_K;}using MPX = PO<MP>;CL D{PU:TTMA<MPX> m_M;MPX m_pt;IN D() : m_M(),m_pt() {};IN D(TTMA<MPX>&& M,MPX&& pt) : m_M(move(M)),m_pt(move(pt)) {}IN D(const D& d) : m_M(d.m_M),m_pt(d.m_pt) {}IN D(D&& d) : m_M(move(d.m_M)),m_pt(move(d.m_pt)) {}IN D& operator=(const D& d) {m_M = d.m_M;m_pt = d.m_pt;return *this;}IN D& operator=(D&& d) {m_M = move(d.m_M);m_pt = move(d.m_pt);return *this;}IN D& operator*=(const D& d) {m_M *= d.m_M;m_pt *= d.m_pt;return *this;}};IN D operator*(const D& d1,const D& d2) {return 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);const MP& CO_zero = MPX::CO_zero();const MP& CO_one = MPX::CO_one();const MP CO_two{2};const MP minus_CO_two{- CO_two};const MP CO_two_inv{(P + 1) / 2};const MPX& zero = MPX::zero();const MPX one{0,CO_one};const MPX X{1,CO_one};const MPX X2_minus_half{2,- CO_two_inv};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);list<list<D> > d_prod{};list<list<int> > over_M{};d_prod.push_front(list<D>());over_M.push_front(list<int>());list<D>& d_prod_init = d_prod.front();list<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(TTMA<MPX>{X * CO_two - CO_two * k,X * k + CO_two_inv * ((1 - k) * k),MPX(one),MPX(zero)}, MPX(one)));over_M_init.push_front(1);}d_prod_init.push_front(D(TTMA<MPX>(1),X - Qt.m_N));over_M_init.push_front(0);k_start = Qt.m_K;}SetProductTree(d_prod);SetProductTree(over_M);list<MA<2,1,MPX> > residue{};residue.push_front(MA<2,1,MPX>(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,MPX> 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){MPX& 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 ? move((itr_d_prod_node->m_M.GetMA22() * *itr_residue) %= pt_node_curr) : MA<2,1,MPX>(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 {const MA<2,1,MP> v{CO_one,CO_zero};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,MPX> MNX{X * minus_CO_two + CO_two * N,X2_minus_half + X * (CO_two_inv + N) ,MPX(one),MPX(zero)};MA<2,1,MP> v_copy{v};SetPRecursiveMAAction(MNX,v_copy,K);cout << v_copy.m_M[0][0] << "\n";}}}RE 0;}