式子
多项式乘法逆
已知 \(F(x)G(x)\equiv 1\;\;(mod\;x^n)\)，\(F(x)H(x)\equiv 1\;\;(mod\;x^{\lceil\frac{n}{2}\rceil})\)，则
\[G(x)\equiv 2H(x)-F(x)H^2(x)\;\;(mod\;x^n) \]多项式开根
\[G(x)\equiv \frac{F(x)+H^2(x)}{2H(x)} \]多项式 ln
\[G(x)\equiv\ln F(x)\;\;(mod\;x^n) \]两边求导
\[G'(x)\equiv(\ln F(x)\;\;(mod\;x^n))' \]\[G'(x)\equiv\ln'F(x)F'(x)\equiv \frac{F'(x)}{F(x)}\;\;(mod\;x^n) \]导数 \((x^a)'=ax^{a-1}\)，积分 \(\int x^adx=\frac{1}{a+1}x^{a+1}\)。
多项式 exp
牛顿迭代：
\[G(x)\equiv \exp{A(x)}\;\;(mod\;x^n) \]已知 \(F(G(x))\equiv 0\;\;(mod\;x^n)\)，\(F(H(x))\equiv 0\;\;(mod\;x^{\lceil\frac{n}{2}\rceil})\)，则
\[G(x)\equiv H(x)-\frac{F(H(x))}{F'(H(x))}\;\;(mod\;x^n) \]
两边取 ln，
\[\ln{G(x)}-A(x)\equiv 0\;\;(mod\;x^n) \]寻找 \(F(G(x))=\ln{G(x)}-A(x)\;\;(mod\;x^n)\) 的零点。
对 \(F(G(x))\) 中 \(F\) 求导时 \(G(x)\) 看作自变量，而 \(A(x)\) 则是常数项，故 \(F'(G(x))=\frac{1}{G(x)}\)。
使用牛顿迭代：
\[\begin{aligned} G(x)&\equiv H(x)-\frac{\ln{H(x)}-A(x)}{\frac{1}{H(x)}}\;\;(mod\;x^n)\\ &\equiv H(x)-H(x)(\ln{H(x)}-A(x))\;\;(mod\;x^n)\\ &\equiv H(x)(1-\ln{H(x)}+A(x))\;\;(mod\;x^n) \end{aligned} \]多项式快速幂
- 次数可以直接取模（模 mod）。
对多项式求 ln，乘次数，再 exp 回去即可。
代码
不封装是因为有些人见个多项式题就把几十 K 的全家桶糊上去···明明用不到这么多
说不定还会把封好的 poly 全压在一行。
我不喜欢。
比我快的基本都比我长。
#include<bits/stdc++.h>
#define EL puts("Elaina")
#define reg register int
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
namespace IO{
const int siz=1<<18;char buf[siz],*p1,*p2;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,siz,stdin),p1==p2)?EOF:*p1++;}
inline int read(){
int x=0;char ch=getc();
while(!isdigit(ch))ch=getc();
while(isdigit(ch))x=x*10+(ch^48),ch=getc();
return x;
}
template<const int mod> inline int readmod(){
int x=0;char ch=getc();
while(!isdigit(ch))ch=getc();
while(isdigit(ch))x=(x*10ll+(ch^48))%mod,ch=getc();
return x;
}
}using IO::read;using IO::readmod;
const int maxn=4e5+3,mod=998244353,inv2=mod+1>>1;
inline int qpow(int a,int b=mod-2){
int ans=1;
for(;b;b>>=1,a=1ll*a*a%mod)
if(b&1)ans=1ll*ans*a%mod;
return ans;
}
int rev[maxn],w[maxn],len=1;
inline void init(int len){
int mid=len>>1;
for(reg i=0;i<len;++i){rev[i]=rev[i>>1]>>1;if(i&1)rev[i]|=mid;}
int wn=qpow(3,(mod-1)/len);w[mid]=1;
for(reg i=mid+1;i<len;++i)w[i]=1ll*w[i-1]*wn%mod;
for(reg i=mid-1;i>0;--i)w[i]=w[i<<1];
}
inline void NTT(int *A,int n){
static ull a[maxn];for(reg i=0;i<n;++i)a[i]=A[rev[i]];
for(reg u=2,v=1;u<=n;v=u,u<<=1)for(reg L=0,t;L<n;L+=u)
for(reg p=L,x=v;p<L+v;++p,++x)t=w[x]*a[p+v]%mod,a[p+v]=a[p]+mod-t,a[p]+=t;
for(reg i=0;i<n;++i)A[i]=a[i]%mod;
}
inline void INTT(int *A,int n){
NTT(A,n),reverse(A+1,A+n);int inv=qpow(n);
for(reg i=0;i<n;++i)A[i]=1ll*A[i]*inv%mod;
}
inline void inverse(int deg,const int *A,int *B){
if(deg==1){B[0]=qpow(A[0]);return;}
inverse(deg+1>>1,A,B);
len=1;while(len<=deg+deg)len<<=1;init(len);
static int F[maxn];memcpy(F,A,deg*sizeof(int));
memset(F+deg,0,(len-deg)*sizeof(int));
memset(B+deg,0,(len-deg)*sizeof(int)),NTT(F,len),NTT(B,len);
for(reg i=0;i<len;++i)B[i]=1ll*B[i]*(2+mod-1ll*F[i]*B[i]%mod)%mod;
INTT(B,len),memset(B+deg,0,(len-deg)*sizeof(int));
}
inline void sqrt(int deg,const int *A,int *B){
if(deg==1){B[0]=1;return;}
static int G[maxn],H[maxn],F[maxn];
sqrt(deg+1>>1,A,G),inverse(deg,G,H);
memcpy(F,A,deg*sizeof(int)),memset(F+deg,0,(len-deg)*sizeof(int));
NTT(F,len),NTT(H,len);
for(reg i=0;i<len;++i)F[i]=1ll*F[i]*H[i]%mod;
INTT(F,len);
for(reg i=0;i<deg;++i)B[i]=1ll*inv2*(F[i]+G[i])%mod;
memset(B+deg,0,(len-deg)*sizeof(int));
}
inline void Dev(int deg,const int *A,int *B){
for(reg i=1;i<deg;++i)B[i-1]=1ll*i*A[i]%mod;B[deg-1]=0;
}
int inv[maxn];
inline void InvDev(int deg,const int *A,int *B){
for(reg i=1;i<deg;++i)B[i]=1ll*inv[i]*A[i-1]%mod;B[0]=0;
}
inline void ln(int deg,const int *A,int *B){
static int F[maxn],G[maxn];
Dev(deg,A,F),inverse(deg,A,G);
memset(F+deg,0,(len-deg)*sizeof(int)),NTT(F,len),NTT(G,len);
for(reg i=0;i<len;++i)F[i]=1ll*F[i]*G[i]%mod;
INTT(F,len),InvDev(deg,F,B),memset(B+deg,0,(len-deg)*sizeof(int));
}
inline void exp(int deg,const int *A,int *B){
if(deg==1){B[0]=1;return;}
static int F[maxn];
exp(deg+1>>1,A,B),ln(deg,B,F);
for(reg i=0;i<deg;++i)F[i]=(A[i]+mod-F[i])%mod;
F[0]=1,NTT(B,len),NTT(F,len);
for(reg i=0;i<len;++i)B[i]=1ll*B[i]*F[i]%mod;
INTT(B,len),memset(B+deg,0,(len-deg)*sizeof(int));
}
inline void power(int deg,const int *A,int k,int *B){
static int F[maxn];ln(deg,A,F);
for(reg i=0;i<deg;++i)F[i]=1ll*k*F[i]%mod;
exp(deg,F,B);
}
int n,F[maxn],G[maxn];
inline void MyDearMoments(){
n=read(),inv[1]=1;
for(reg i=2;i<n;++i)inv[i]=mod-1ll*mod/i*inv[mod%i]%mod;
}
int main(){return MyDearMoments(),0;}