多项式，清空，封装，边界，是讨厌的。
NTT
懒得讲原理，喵。
ll A[maxn],B[maxn],pos[maxn],S[maxn];
const int mod=998244353,g=3,ginv=332748118;
ll ksm(ll x,int y)
{
ll ret=1;
while(y)
{
if(y&1) ret=ret*x%mod;
x=x*x%mod; y>>=1;
}
return ret;
}
int pre(int n,int m)
{
int lim=0;
while((1<<lim)<=n+m) lim++;
for(int i=0;i<=(1<<lim);i++)
pos[i]=(pos[i>>1]>>1)|((i&1)<<(lim-1));
return lim;
}
void NTT(ll *f,ll n,int opt)
{
for(int i=0;i<n;i++) if(i<pos[i]) swap(f[i],f[pos[i]]);
for(int i=1;i<n;i<<=1)
{
ll step=ksm((opt>0?g:ginv),(mod-1)/(2*i));
for(int j=0;j<n;j+=i+i)
{
ll cur=1;
for(int k=j;k<j+i;k++)
{
int gx=f[k],hx=1ll*cur*f[k+i]%mod;
f[k]=(gx+hx)%mod;f[k+i]=(gx-hx+mod)%mod;
cur=cur*step%mod;
}
}
}
if(opt==-1)
{
int ninv=ksm(n,mod-2);
for(int i=0;i<n;i++) f[i]=f[i]*ninv%mod;
}
}
void MUL(ll *s,ll *f,ll *h,int n,int m)
{
int lim=pre(n,m);
for(int i=0;i<=n;i++) A[i]=f[i];
for(int i=0;i<=m;i++) B[i]=h[i];
for(int i=n+1;i<=(1<<lim);i++) A[i]=0;
for(int i=m+1;i<=(1<<lim);i++) B[i]=0;
NTT(A,(1<<lim),1);NTT(B,(1<<lim),1);
for(int i=0;i<=(1<<lim)-1;i++) s[i]=A[i]*B[i]%mod;
NTT(s,(1<<lim),-1);
}
多项式求逆
给出\(F(x)\),求出 \(G(x)\) 使得 \(G(x) F(x)\equiv 1 (\mod x^n)\)
令 \(F(x)H(x)\equiv 1(\mod x^{\frac n 2})\)
\(F(x)(G(X)-H(x))\equiv 0(\mod x^{\frac n 2})\)
\(G(x)-H(x)\equiv 0(\mod x^{\frac n 2})\)
\((G(x)-H(x))^2\equiv 0(\mod x^{n})\)
\(G^2(x)-2G(x)H(x)+H^2(x)\equiv 0(\mod x^n)\)
两边同时乘个 \(F(x)\)
\(G(x)-2H(x)+F(x)H^2(x)\equiv 0(\mod x^n)\)
\(G(x)=2H(x)-F(x)H^2(x)\)
然后已知 \(H(x)\) 就能做了。递归下去就行了。。
一般都写成非递归。
void INV(ll *s,ll *f,int n)
{
S[0]=ksm(f[0],mod-2);S[1]=0;
for(int len=2;len<=(n<<1);len<<=1)
{
ll lim=(len<<1);
for(int i=0;i<len;i++) A[i]=f[i],B[i]=S[i];
for(int i=len;i<lim;i++) A[i]=B[i]=0;
pre(len,0);
NTT(A,lim,1); NTT(B,lim,1);
for(int j=0;j<lim;j++)
S[j]=(2*B[j]%mod+mod-A[j]*B[j]%mod*B[j]%mod)%mod;
NTT(S,lim,-1);
for(int j=len;j<lim;j++) S[j]=0;
}
for(int i=0;i<=n;i++) s[i]=S[i];
}
多项式对数函数（ln）
设 \(G(x)=\ln(F(X))\)
同时求导
\(G'(x)=\ln '(F(x))\)
然后复合函数求导拆开
\(G'(x)=\frac{F'(x)}{F(x)}\)
然后先求导，再求逆，最后积分一下就行。
求导：\((x^\alpha)' = \alpha x^{\alpha -1}\)
积分：\(\int \alpha x^{\alpha-1}=x^{\alpha}\)
\(\int x^\alpha=\frac 1 {\alpha+1} x^{\alpha+1}\)
留个坑（（（
标签：frac,int,多项式,ll,笔记,alpha,mod,equiv From： https://www.cnblogs.com/cc0000/p/17009204.html