为了方便，下文中的多项式长度和 $n$ 均为 $2$ 的幂（多项式除法、三角函数和反三角函数除外），模数均为 $998244353$。
下面所有函数中（除了 NTT_init）传进去的 $n,m$ 都是多项式项数而不是次数。
多项式乘法
这是前置知识，如果不会建议「点开洛谷题面单击右边蓝色按钮题解」。
int r[N];
void NTT(int* A,int n,int op) {
for (int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]);
for (int i=1;i<n;i<<=1) {
int rot=qpow(op==1?3:332748118,(mod-1)/(i<<1));
for (int j=0;j<n;j+=i<<1)
for (int k=0,w=1;k<i;++k,w=1ll*w*rot%mod) {
int x=A[j+k],y=1ll*w*A[j+k+i]%mod;
A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod;
}
}
if (op==-1) { int inv=qpow(n,mod-2);
for (int i=0;i<n;++i) A[i]=1ll*A[i]*inv%mod;
}
}
int NTT_init(int n) {
int lim=1,l=-1;
for (;lim<n;lim<<=1,++l);
for (int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<l);
return lim;
}多项式求导
$$
(x^a)'=ax^{a-1}
$$
void getderi(int* F,int* G,int n) {
for (int i=1;i<n;++i) G[i-1]=1ll*F[i]*i%mod;
G[n-1]=0;
}多项式不定积分
$$
\int x^a\mathrm{d}x=\frac{x^{a+1}}{a+1}
$$
void getinte(int* F,int* G,int n) {
for (int i=1;i<n;++i) G[i]=1ll*F[i-1]*qpow(i,mod-2)%mod;
G[0]=0;
}多项式牛顿迭代
已知 $G(x)$，求 $F(x)$ 满足 $G(F(x))\equiv 0\pmod{x^n}$。
假设我们已经求出了 $F_o(x)$ 满足 $G(F_0(x))\equiv 0\pmod{x^{\frac{n}{2}}}$，将 $G(x)$ 在 $F_0(x)$ 处泰勒展开得到
$$
G(F(x))=\sum_{i=0}^{+\infty}\frac{G^{(i)}(F_0(x))}{i!}(F(x)-F_0(x))^i
$$
可以发现 $i\geq 2$ 时在模 $x^n$ 意义下都为 $0$，所以
$$
G(F(x))\equiv G(F_0(x))+G'(F_0(x))(F(x)-F_0(x))\pmod{x^n}
$$
又 $G(F(x))=0$，化简得到
$$
F(x)=F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}\pmod{x^n}
$$
多项式求逆
已知 $F(x)$，求 $G(x)$ 满足 $F(x)G(x)\equiv 1\pmod{x^n}$。
假设我们已经求出了 $G_0(x)$ 满足 $F(x)G_0(x)\equiv 1\pmod{x^{\frac{n}{2}}}$，那么
$$
F(x)(G(x)-G_0(x))\equiv 0\pmod{x^\frac{n}{2}}
$$
所以
$$
G(x)-G_0(x)\equiv 0\pmod{x^{\frac{n}{2}}}
$$
平方得到
$$
G(x)^2-2G(x)G_0(x)+G_0(x)^2\equiv 0\pmod{x^n}
$$
乘上 $F(x)$ 即可得到
$$
G(x)\equiv 2G_0(x)-F(x)G_0(x)^2\pmod{x^n}
$$
这样就可以由 $G_0(x)$求出 $G(x)$ 了。
void getinv(int* F,int* G,int n) {
static int A[N],B[N];
if (n==1) { G[0]=qpow(F[0],mod-2); return; }
getinv(F,G,n>>1);
for (int i=0;i<n;++i) A[i]=F[i],B[i]=G[i];
int lim=NTT_init(n<<1);
NTT(A,lim,1),NTT(B,lim,1);
for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod*B[i]%mod;
NTT(A,lim,-1);
for (int i=0;i<n;++i) G[i]=(2ll*G[i]-A[i]+mod)%mod;
for (int i=0;i<lim;++i) A[i]=B[i]=0;
}多项式对数函数
已知 $F(x)$，求 $G(x)$ 满足 $G(x)\equiv\ln F(x)\pmod{x^n}$。保证 $F(x)$ 常数项为 $1$。
两边求导得到
$$
G'(x)\equiv\ln'(F(x))F'(x)\pmod{x^n}
$$
即
$$
G'(x)\equiv\frac{F'(x)}{F(x)}\pmod{x^n}
$$
求导+求逆后乘起来再不定积分回去即可。
void getln(int* F,int* G,int n) {
static int A[N],B[N];
getderi(F,A,n),getinv(F,B,n);
int lim=NTT_init(n<<1);
NTT(A,lim,1),NTT(B,lim,1);
for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod;
NTT(A,lim,-1);
getinte(A,G,n);
for (int i=0;i<lim;++i) A[i]=B[i]=0;
}多项式指数函数
已知 $F(x)$，求 $G(x)$ 满足 $G(x)\equiv e^{F(x)}\pmod{x^n}$。保证 $F(x)$ 常数项为 $0$。
两边取对数得到
$$
\ln G(x)-F(x)\equiv 0\pmod{x^n}
$$
不妨设 $H(G(x))\equiv \ln G(x)-F(x)\pmod{x^n}$，套牛顿迭代得到
$$
\begin{aligned}
G(x)&\equiv G_0(x)-\frac{H(G_0(x))}{H'(G_0(x))}\pmod{x^n}\\
&\equiv G_0(x)-\frac{\ln G_0(x)-F(x)}{\frac{1}{G_0(x)}}\pmod{x^n}\\
&\equiv G_0(x)(1-\ln G_0(x)+F(x))\pmod{x^n}
\end{aligned}
$$
void getexp(int* F,int* G,int n) {
static int A[N],B[N];
if (n==1) { G[0]=1; return; }
getexp(F,G,n>>1);
for (int i=0;i<n;++i) A[i]=G[i];
getln(G,B,n);
for (int i=0;i<n;++i) B[i]=(mod-B[i]+F[i])%mod;
B[0]=(B[0]+1)%mod;
int lim=NTT_init(n<<1);
NTT(A,lim,1),NTT(B,lim,1);
for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod;
NTT(A,lim,-1);
for (int i=0;i<n;++i) G[i]=A[i];
for (int i=0;i<lim;++i) A[i]=B[i]=0;
}多项式幂函数
已知 $F(x)$ 和 $k$，求 $G(x)$ 满足 $G(x)\equiv F(x)^k\pmod{x^n}$。保证 $F(x)$ 常数项为 $1$。
求 $\ln$ 后将系数乘上 $k$ 再 $\exp$ 回去即可。
void getpow(int* F,int* G,int n,int k) {
static int A[N];
getln(F,A,n);
for (int i=0;i<n;++i) A[i]=1ll*A[i]*k%mod;
getexp(A,G,n);
for (int i=0;i<n;++i) A[i]=0;
}如果不保证常数项为 $1$，可以先提一个 $a\times x^b$ 出来转化成常数项为 $1$ 的情况，最后再乘回去。
多项式开根
已知 $F(x)$，求 $G(x)$ 满足 $G(x)^2\equiv F(x)\pmod{x^n}$，多解保留常数项较小的那一个。
移项得到
$$
G(x)^2-F(x)\equiv 0\pmod{x^n}
$$
不妨设 $H(G(x))\equiv G(x)^2-F(x)\pmod{x^n}$，套牛顿迭代得到
$$
\begin{aligned}
G(x)&\equiv G_0(x)-\frac{H(G_0(x))}{H'(G_0(x))}\pmod{x^n}\\
&\equiv G_0(x)-\frac{G_0(x)^2-F(x)}{2G_0(x)}\pmod{x^n}\\
&\equiv \frac{G_0(x)}{2}+\frac{F(x)}{2G_0(x)}
\end{aligned}
$$
void getsqrt(int* F,int* G,int n) {
static int A[N],B[N];
if (n==1) { G[0]=Cipolla::calc(F[0]); return; }
getsqrt(F,G,n>>1);
for (int i=0;i<n;++i) A[i]=F[i];
getinv(G,B,n);
int lim=NTT_init(n<<1);
NTT(A,lim,1),NTT(B,lim,1);
for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod;
NTT(A,lim,-1);
for (int i=0;i<n;++i) G[i]=1ll*(A[i]+G[i])*inv2%mod;
for (int i=0;i<lim;++i) A[i]=B[i]=0;
}那个 Cipolla::calc 是求二次剩余。
多项式除法
根据题意有
$$
F(x)=G(x)Q(x)+R(x)
$$
即
$$
F(\frac{1}{x})=G(\frac{1}{x})Q(\frac{1}{x})+R(\frac{1}{x})
$$
两边同乘 $x^n$
$$
x^nF(\frac{1}{x})=x^mG(\frac{1}{x})x^{n-m}Q(\frac{1}{x})+x^nR(\frac{1}{x})
$$
可以发现 $x^nF(\frac{1}{x})$ 就是 $F(x)$ 系数翻转后得到的多项式，于是有
$$
F_R(x)=G_R(x)Q_R(x)+x^{n-m+1}R_R(x)
$$
因为 $Q_R(x)$ 是 $n-m$ 次式，所以我们模上 $x^{n-m+1}$
$$
F_R(x)\equiv G_R(x)Q_R(x)\pmod{x^{n-m+1}}
$$
即
$$
Q_R(x)\equiv\frac{F_R(x)}{G_R(x)}\pmod{x^{n-m+1}}
$$
多项式求逆即可。
求 $R(x)$ 就很简单了
$$
R(x)=F(x)-G(x)Q(x)
$$
void getdiv(int *F,int *G,int n,int m,int *Q,int *R) {
static int B[N],AR[N],BR[N],iBR[N];
for (int i=0;i<n;++i) AR[n-i-1]=F[i];
for (int i=0;i<m;++i) B[i]=G[i],BR[m-i-1]=G[i];
int lim1=1; for (;lim1<n-m+1;lim1<<=1);
getinv(BR,iBR,lim1);
int lim=NTT_init(n+lim1);
NTT(iBR,lim,1),NTT(AR,lim,1);
for (int i=0;i<lim;++i) Q[i]=1ll*iBR[i]*AR[i]%mod;
NTT(Q,lim,-1);
for (int i=n-m+1;i<lim;++i) Q[i]=0;
reverse(Q,Q+n-m+1);
lim=NTT_init(n);
NTT(B,lim,1),NTT(Q,lim,1);
for (int i=0;i<lim;++i) R[i]=1ll*B[i]*Q[i]%mod;
NTT(Q,lim,-1),NTT(R,lim,-1);
for (int i=0;i<lim;++i) R[i]=(F[i]-R[i]+mod)%mod;
for (int i=m-1;i<lim;++i) R[i]=0;
for (int i=0;i<lim;++i) B[i]=AR[i]=BR[i]=iBR[i]=0;
}多项式三角函数
根据欧拉公式有
$$
e^{ix}=\cos x+i\sin x
$$
同理有
$$
e^{-ix}=\cos x-i\sin x
$$
所以
$$
\begin{aligned}
\sin x&=\frac{e^{ix}-e^{-ix}}{2i}\\
\cos x&=\frac{e^{ix}+e^{-ix}}{2}
\end{aligned}
$$
多项式 exp 即可。
有一个问题是这个 $i$ 是啥，其实就是 $-1$ 在模 $998244353$ 意义下的二次剩余。
void getsin(int *F,int *G,int n) {
static int A[N],B[N],C[N];
for (int i=0;i<n;++i) A[i]=1ll*F[i]*img%mod;
getexp(A,B,n),getinv(B,C,n);
int inv=qpow(img<<1,mod-2);
for (int i=0;i<n;++i) G[i]=1ll*(B[i]-C[i]+mod)*inv%mod;
for (int i=0;i<n;++i) A[i]=B[i]=C[i]=0;
}
void getcos(int *F,int *G,int n) {
static int A[N],B[N],C[N];
for (int i=0;i<n;++i) A[i]=1ll*F[i]*img%mod;
getexp(A,B,n),getinv(B,C,n);
int inv=qpow(2,mod-2);
for (int i=0;i<n;++i) G[i]=1ll*(B[i]+C[i])*inv%mod;
for (int i=0;i<n;++i) A[i]=B[i]=C[i]=0;
}多项式反三角函数
先考虑 $\arcsin$。
$$
G(x)\equiv\arcsin F(x)\pmod{x^n}
$$
两边求导得到
$$
G'(x)\equiv\frac{F'(x)}{\sqrt{1-F(x)^2}}\pmod{x^n}
$$
再不定积分
$$
G(x)\equiv\int\frac{F'(x)}{\sqrt{1-F(x)^2}}\mathrm{d}x\pmod{x^n}
$$
多项式求导+开根+求逆+不定积分即可。
接着考虑 $\arccos$，同理可得
$$
G(x)\equiv-\int\frac{F'(x)}{\sqrt{1-F(x)^2}}\mathrm{d}x\pmod{x^n}
$$
$\arctan$ 也一样
$$
G(x)\equiv\int\frac{F'(x)}{1+F(x)^2}\mathrm{d}x\pmod{x^n}
$$
void getarcsin(int *F,int *G,int n) {
static int A[N],B[N],C[N],D[N];
for (int i=0;i<n;++i) A[i]=F[i];
int lim=NTT_init(n<<1);
NTT(A,lim,1);
for (int i=0;i<lim;++i) A[i]=1ll*A[i]*A[i]%mod;
NTT(A,lim,-1);
for (int i=n;i<lim;++i) A[i]=0;
for (int i=0;i<n;++i) A[i]=(mod-A[i])%mod;
++A[0]; getsqrt(A,B,n); getinv(B,C,n); getderi(F,D,n);
lim=NTT_init(n<<1);
NTT(C,lim,1),NTT(D,lim,1);
for (int i=0;i<lim;++i) D[i]=1ll*C[i]*D[i]%mod;
NTT(D,lim,-1);
getinte(D,G,n);
for (int i=0;i<lim;++i) A[i]=B[i]=C[i]=D[i]=0;
}
void getarccos(int *F,int *G,int n) {
getarcsin(F,G,n);
for (int i=0;i<n;++i) G[i]=(mod-G[i])%mod;
}
void getarctan(int *F,int *G,int n) {
static int A[N],B[N],C[N];
for (int i=0;i<n;++i) A[i]=F[i];
int lim=NTT_init(n<<1);
NTT(A,lim,1);
for (int i=0;i<lim;++i) A[i]=1ll*A[i]*A[i]%mod;
NTT(A,lim,-1);
for (int i=n;i<lim;++i) A[i]=0;
++A[0]; getinv(A,B,n); getderi(F,C,n);
lim=NTT_init(n<<1);
NTT(B,lim,1),NTT(C,lim,1);
for (int i=0;i<lim;++i) C[i]=1ll*B[i]*C[i]%mod;
NTT(C,lim,-1);
getinte(C,G,n);
for (int i=0;i<lim;++i) A[i]=B[i]=C[i]=0;
}多项式多点求值
鸽了。
多项式快速插值
鸽了。
2 条评论
stO M_sea Orz 并且催更多项式复合
不会 ::QQ:Y.qq9::