多项式总结&多项式板子
三角/反三角是不可能放的（也不可能真香的
多项式乘法（DFT,FFT,NTT,MTT）
背板子
前置知识：泰勒展开
如果(f(x))在(x_0)处存在(n)阶导，那么
称作(f(x))在(x_0)处的泰勒展开。
前置知识：牛顿迭代
有一个(n-1)次多项式(A(x))，你需要求(B(x))满足(A(B(x))equiv 0(mod x^n))
如果(n=1)就只有常数项，直接计算就行了
否则令(m=lceilfrac n2 ceil)，递归地求(B_m(x))。（(B_m(x)=B(x)mod x^m)）
然后根据(B_m)和(A)推出(B_n)。
(A(B_n(x)))在(B_m(x))处泰勒展开，(A(B_n(x))=A(B_m(x))+A'(B_m(x))(B_n(x)-B_m(x)))
（然后后面的因为((B_n(x)-B_m(x)))是(x^m)的倍数，而结果要(mod x^n)所以都没了）
左边为0，化简得到了(B_n(x)=B_m(x)-frac{A(B_m(x))}{A'(B_m(x))})
如果推的过程是(O(nlog n))，那么总复杂度是(T(n)=T(n/2)+O(nlog n)=O(nlog n))很小但常数就不一定了
多项式求导/积分
只需要知道((x^n)'=nx^{n-1})，(int(x^n)=frac{1}{n+1}x^{n+1})就行了
多项式求逆
有一个(n-1)次多项式(A(x))，你要求(B(x))满足(A(x)B(x)equiv 1(mod x^n))
用牛顿迭代做。
(A(x)B(x)=1)，设(F(B(x))=A(x)B(x)-1)，那么要求(F(B(x))=0)。
带入上面的式子，(B_n(x)=B_m-frac{AB_m-1}{A})
注意(B)是(A)的逆，所以化简(B_n(x)=2B_m(x)-AB_m^2(x))
多项式开根
有一个(n-1)次多项式(A(x))，你要求(B(x))满足(B(x)^2equiv A(x)(mod x^n))
同上，构造(F(B(x))=B(x)^2-A(x)=0)。
代入，(B_n(x)=B_m(x)-frac{B_m(x)^2-A(x)}{2B_m(x)})
化简，(B_n(x)=frac 12(B_m(x)+frac{A(x)}{B_m(x)}))
多项式(ln)
不用牛顿迭代
有一个(n-1)次多项式(A(x))，你要求(B(x))满足(B(x)=ln A(x)(mod x^n))
注意多项式函数必须要满足常数项在膜意义下可以做，比如(ln)保证常数项为(1)
(B(x)=ln A(x))
(B'(x)=(ln A(x))'=frac{A'(x)}{A(x)})
(B(x)=int frac{A'(x)}{A(x)})
多项式(exp)
这个常数略大，可能被分治(NTT)吊打。
有一个(n-1)次多项式(A(x))，你要求(B(x))满足(A(x)=ln B(x)(mod x^n))
牛顿迭代，(F(B(x))=ln B(x)-A(x)=0)
化简，(B_n(x)=B_m(x)(1-ln(B_m(x))+A(x)))
多项式快速幂
先求(ln)，然后乘(k)，再(exp)回去。
虽然是(O(nlog n))但是常数不知道几个(log)了
开根忘了求可以用常数巨大的(exp)
多项式带余除法（取膜）
(F(x)=G(x)Q(x)+R(x))，已知(F,G)分别是次数为(n-1,m-1(n>m))的多项式，(Q)是次数为(n-m)的多项式，(R)次数小于(m-1)。求(Q,R)
因为结论很好记就直接记结论了。
(Q^R=F^R{G^R}^{-1}mod x^{n-m})
(R=F-GQ)
就做完了。
板子，vector写的，没卡常警告
//================多项式板子部分===================
#define mod 998244353
#define maxn 262147
#define Gmod 3
#define poly std::vector<int>
il int pow(int x,int y){
int ret=1;
while(y){
if(y&1)ret=1ll*ret*x%mod;
x=1ll*x*x%mod;y>>=1;
}
return ret;
}
int rev[maxn],_lstN,P[maxn],iP[maxn];
il vd ntt(int*A,int N,int t){
for(int i=0;i<N;++i)if(rev[i]>i)std::swap(A[i],A[rev[i]]);
for(int o=1;o<N;o<<=1){
int W=t?P[o]:iP[o];
for(int*p=A;p!=A+N;p+=o<<1)
for(int i=0,w=1;i<o;++i,w=1ll*w*W%mod){
int t=1ll*w*p[i+o]%mod;
p[i+o]=(p[i]-t+mod)%mod;p[i]=(p[i]+t)%mod;
}
}
if(!t){
int inv=pow(N,mod-2);
for(int i=0;i<N;++i)A[i]=1ll*A[i]*inv%mod;
}
}
int N,lg;
il vd setN(int n){
N=1,lg=0;
while(N<n)N<<=1,++lg;
if(N!=_lstN)for(int i=0;i<N;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<lg-1);
}
il vd ntt(poly&a,int t){
static int A[maxn];
for(int i=0;i<a.size();++i)A[i]=a[i];memset(A+a.size(),0,4*(N-a.size()));
ntt(A,N,t);
a.resize(N);
for(int i=0;i<N;++i)a[i]=A[i];
int s=a.size();while(s&&!a[s-1])--s;
a.resize(s);
}
il poly mul(poly a,poly b,int newn=-1){
if(newn==-1)newn=a.size()+b.size()-1;
setN(a.size()+b.size()-1);
ntt(a,1),ntt(b,1);
for(int i=0;i<N;++i)a[i]=1ll*a[i]*b[i]%mod;
ntt(a,0);a.resize(newn);
return a;
}
il poly operator+(poly a,const poly&b){
if(a.size()<b.size())a.resize(b.size());
for(int i=0;i<a.size();++i)if(i<b.size())a[i]=(a[i]+b[i])%mod;
return a;
}
il poly operator-(poly a,const poly&b){
if(a.size()<b.size())a.resize(b.size());
for(int i=0;i<a.size();++i)if(i<b.size())a[i]=(a[i]-b[i]+mod)%mod;
return a;
}
il poly operator*(poly a,int b){
for(auto&i:a)i=1ll*i*b%mod;
return a;
}
il poly qiudao(poly a){
for(int i=0;i<a.size()-1;++i)a[i]=1ll*a[i+1]*(i+1)%mod;
a.erase(a.end()-1);
return a;
}
il poly jifen(poly a){
a.insert(a.begin(),0);
for(int i=1;i<a.size();++i)a[i]=1ll*a[i]*pow(i,mod-2)%mod;
return a;
}
il poly getinv(poly a){
if(a.size()==1)return poly(1,pow(a[0],mod-2));
int n=a.size(),m=a.size()+1>>1;
poly _a(m);
for(int i=0;i<m;++i)_a[i]=a[i];
poly b=getinv(_a);
setN(n+m*2-2);
ntt(a,1);ntt(b,1);
for(int i=0;i<N;++i)a[i]=1ll*a[i]*b[i]%mod*b[i]%mod;
ntt(a,0),ntt(b,0);
a.resize(n);
return b*2-a;
}
il poly getln(poly a,int n=-1){
if(n==-1)n=a.size();
a.resize(n);
return jifen(mul(qiudao(a),getinv(a),n));
}
il poly getexp(poly a){
if(a.size()==1)return a[0]=1,a;
int n=a.size(),m=a.size()+1>>1;
poly _a(m);
for(int i=0;i<m;++i)_a[i]=a[i];
poly b=getexp(_a);
return mul(b,poly(1,1)-getln(b,a.size())+a,a.size());
}
il poly operator^(poly a,int b){
int n=a.size();
a=getexp(getln(a)*b);a.resize(n);
return a;
}
il poly operator%(poly a,poly b){
int n=a.size(),m=b.size();
if(n<m)return a;
std::reverse(a.begin(),a.end());
std::reverse(b.begin(),b.end());
b.resize(n);
poly c=mul(a,getinv(b),n-m+1);
std::reverse(a.begin(),a.end());
b.resize(m);std::reverse(b.begin(),b.end());
std::reverse(c.begin(),c.end());
a=a-mul(b,c);
int s=a.size();while(s&&!a[s-1])--s;
a.resize(s);
return a;
}
il poly sqrt(poly a){
if(a.size()==1)return a;
int n=a.size(),m=a.size()+1>>1;
poly _a(m);
for(int i=0;i<m;++i)_a[i]=a[i];
poly b=sqrt(_a);b.resize(n);
return (b+mul(a,getinv(b),n))*(mod+1>>1);
}
il vd poly_init(){
int G=Gmod,iG=pow(G,mod-2);
for(int i=1;i<maxn;i<<=1)P[i]=pow(G,(mod-1)/(i<<1)),iP[i]=pow(iG,(mod-1)/(i<<1));
}
struct _poly_auto_init{_poly_auto_init(){poly_init();}}_auto_init;
//End==============多项式板子部分===================