多项式全家桶

九月 01, 2021

多项式全家桶

导数公式

$(C)^{‘}=0$ $(x^\mu)’=\mu x^{\mu-1}$

$(a^x)’=a^x\ln x$ ( $a$ 为常数） $(\sin x)’=\cos x$

$(\cos x)’=-\sin x$ $(\tan x)’=\sec^2x$

$(\cot x)’=-\csc^2x$ $(\sec x)’=\sec x \cot x$

$(\csc x)’=-\csc x\cot x$ $(\ln x)’=\dfrac{1}{x}$

$({\log_a}^x)’=\dfrac{1}{x\ln a}$ $(e^x)’=e^x$

加减公式：

$(u\pm v)’=u’\pm v’$ $(Cu)’=Cu’$ （C是常数）

$(uv)’=u’v+uv’$ $(\dfrac{u}{v})’=(\dfrac{u’v-uv’}{v^2})$

FFT

复数

设$a,b$为实数，$i^2=-1$，形如$a+bi$的数叫复数，其中$i$被称为虚数单位，复数域是目前已知最大的域

在复平面中，$x$ 代表实数，$y$ 轴（除原点外的点）代表虚数，从原点$(0,0)$到$(a,b)$的向量表示复数$a+bi$

模长：从原点$(0,0)$到点$(a,b)$的距离，即$\sqrt{a^2+b^2}$

幅角：假设以逆时针为正方向，从xx轴正半轴到已知向量的转角的有向角叫做幅角

计算：平行四边形法则(其实就是分配律)，注意这里的$i^2$为-1：

几何定义：复数相乘，模长相乘，幅角相加~~(至今我也没看懂)~~

$(a+bi)\times (c+di)=ac+bdi^2+bci+adi=ac-bd+(bc+ad)i$

多项式表示法

系数表示法：

设$A(x)$表示一个$x-1$次多项式

则$A(x)=\sum_{i=0}^{n} a_i * x^i$

例如：$A(3)=2+3\times x+x^2$

利用这种方法计算多项式乘法复杂度为$O(n^2)$

（第一个多项式中每个系数都需要与第二个多项式的每个系数相乘）

利用这种方法计算多项式乘法的时间复杂度为$O(n^2)$

点值表示法

将 $n$ 互不相同的 $x$ 带入多项式，会得到 $n$ 个不同的取值 $y$

则该多项式被这 $n$ 个点 $(x_1,y_1),(x_2,y_2)\dots(x_n,y_n)$ 唯一确定

其中$y_i=\sum_{j=0}^{n-1} a_j\times x_i^j$

例如：上面的例子用点值表示法可以为$(0,2)~(1,5)~(2,12)$

利用这种方法计算多项式乘法的时间复杂度仍然为$O(n^2)$

可以发现，大整数乘法复杂度的瓶颈可能在“多项式转换成点值表示”这一步（以及其反向操作），只要完成这一步就可以$O(n)$求答案了。

单位根

定义

在后面我们默认 $n$ 为 2 的整数次幂

在复平面上，以原点为圆心，1为半径作圆，所得的圆叫单位圆。以圆点为起点，圆的$n$等分点为终点，做$n$个向量，设幅角为正且最小的向量对应的复数为$\omega_n$，称为$n$次单位根。

根据复数乘法的运算法则，其余$n-1$个复数为$\omega_n^2,\omega_n^3\ldots\omega_n^n$

就算他们的值，我们可以用欧拉公式：$\omega_{n}^{k}=\cos\ k \dfrac{2\pi}{n}+i\sin k\dfrac{2\pi}{n}$

单位根的幅角为周角的$\dfrac{1}{n}$

在代数中，若$z^n=1$，我们把$z$称为$n$次单位根

单位根的性质与反演

单位根的性质：

$\omega _n ^k =\cos~k\dfrac{2\pi}{n}+i\times \sin~k\dfrac{2\pi}{n}$
$\omega _{2n}^{2k}=\omega _n^k$
$\omega_n^{k+\frac{n}{2}}=-\omega _n^k$
$\omega_n^0=\omega _n^n=1$

第二条的证明：

$\omega ^{2k}_{2n}=\cos ~2k\dfrac{2\pi}{2n}+i\sin2k\dfrac{2\pi}{2n}$

约分后就和原来一样了

第三条同上，约分即可

单位根反演：

$\forall k,[n\mid k]=\dfrac{1}{n}\sum_{i=0}^{n-1}w_n^{ik}\dots①$

证明：

当$~k\mid n$ 时：由 $\omega_n^0=\omega_n^n~~~$得:$\omega_n^{ik}=1$故原式等于1

当 $k\nmid n$ 时：原式乘上$\omega_n^k$可化成

$\dfrac{1}{n}\sum_{i=1}^{n}w_n^{ik}\dots②$

②减①得：

$\dfrac{1}{n}\dfrac{\omega_{n}^{nk}-\omega_n^0}{\omega_n^k-1}$

易得上式为0

complex

C++的STL提供了复数模板！
头文件：#include <complex>
定义： complex<double> x;
运算：直接使用加减乘除

快速傅里叶变换（FFT）

为什么要使用单位根作为$x$代入

规定我们带入的点值为$n$个单位根

设$(y_0,y_1,y_2\dots y_{n-1})$为多项式$A(x)$的离散傅里叶变换（即把$\omega_n^0,\omega_n^1\dots\omega_n^{n-1}$代入上式后的结果）

我们再设一个多项式$B(x)$其各位系数为上述的$y$

现在，我们把上述单位根的倒数，即$\omega_n^{-1},\omega_n^{-2}\dots\omega_n^{1-n}$代入$B(x)$得$(z_0,z_1\dots z_{n-1})$，那么有

$\begin{eqnarray} z_k&=&\sum_{i=0}^{n-1}y_i(\omega_n^{-k})^i\\ &=&\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}a_j(\omega_n^i)^j)(\omega_n^{-k})^i \\&=&\sum_{i=0}^{n-1}a_j(\sum_{j=0}^{n-1}(\omega_n^{j-k})^i) \end{eqnarray}$

最下面括号里的式子$\sum_{j=0}^{n-1}(\omega_n^{j-k})^i$显然是能求的

当 $k=j$ 时，该式为$n$

当 $k\ne j$ 时

通过等比数列求和可以得出

$\dfrac{(\omega_n^{j-k})^n-1}{\omega_n^{j-k}-1}=\dfrac{1-1}{\omega_n^{j-k}-1}=0$

所以我们有

$z_k=na_k$

因此我们可以发现：

把多项式$A(x)$的离散傅里叶变换结果作为另一个多项式$B(x)$的系数，取单位根的倒数即$\omega ^0_n,\omega ^{−1}_n,\omega ^{−2}_n,…,\omega ^{-(n−1)}_n$作为$x$代入$B(x)$，得到的每个数再除以$n$，得到的就是$A(x)$的各项系数

快速傅里叶变换的数学证明

我们考虑把一个普通的多项式按奇偶性分类，有：

$A(x)=(a_0+a_2\times x^2+a_4\times x^4+⋯+a_{n−2}\times x^{n−2})+(a_1\times x+a_3\times x^3+a_5\times x^5+⋯+a_{n−1}\times x^{n−1})$

所以我们设成两个多项式：

$A_1(x)=a_0+a_2x+a_4x^2+⋯+a_{n−2}x^{\frac{n}{2}-1}$

$A_2(x)=a_1+a_3x+a_5x^2+⋯+a_{n−1}x^{\frac{n}{2}-1}$

因此$A(x)=A_1(x^2)+xA_2(x^2)$

假设当前$k<\frac{n}{2}$，现再我们要代入$x=\omega_n^k$

$\begin{eqnarray} A(\omega_n^k)&=&A_1(\omega_n^{2k})+\omega_n^kA_2(\omega^{2k}_n) \\&=&A1(\omega_{\frac{n}{2}}^{k})+\omega_n^kA_2(\omega^k_{\frac{n}{2}}) \end{eqnarray}$

我们再代入$x=\omega_n^{k+\frac{n}{2}}$

$\begin{eqnarray} A(\omega_n^{k+\frac{n}{2}})&=&A_1(\omega_n^{2k+n})+\omega_n^{k+\frac{n}{2}}A_2(\omega^{2k+n}_n) \\&=&A1(\omega_{\frac{n}{2}}^{k})-\omega_n^kA_2(\omega^k_{\frac{n}{2}}) \end{eqnarray}$

因此，只要我们求出$A_1(x)$和$A_2(x)$分别在$\omega_{\frac{n}{2}}^0,\omega_{\frac{n}{2}}^1,\omega_{\frac{n}{2}}^2$等的点值表示，就可以$O(n)$的求出$A(x)$的点值表示了。分治的边界是$n=1$

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=2*1e6+10;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const double Pi=acos(-1.0);
struct complex{
    double x,y;
    complex (double xx=0,double yy=0){x=xx,y=yy;}
}a[MAXN],b[MAXN];
complex operator + (complex a,complex b){ return complex(a.x+b.x , a.y+b.y);}
complex operator - (complex a,complex b){ return complex(a.x-b.x , a.y-b.y);}
complex operator * (complex a,complex b){ return complex(a.x*b.x-a.y*b.y , a.x*b.y+a.y*b.x);}
void fast_fast_tle(int len,complex *a,int type){
    if(len==1) return ;
    complex a1[len>>1],a2[len>>1];
    for(int i=0;i<=len;i+=2) a1[i>>1]=a[i],a2[i>>1]=a[i+1];
    fast_fast_tle(len>>1,a1,type);
    fast_fast_tle(len>>1,a2,type);
    complex Wn=complex(cos(2.0*Pi/len),type*sin(2.0*Pi/len)),w=complex(1,0);
    for(int i=0;i<(len>>1);i++,w=w*Wn)
        a[i]=a1[i]+w*a2[i],
        a[i+(len>>1)]=a1[i]-w*a2[i];
}
int main(){
    int N=read(),M=read();
    for(int i=0;i<=N;i++) a[i].x=read();
    for(int i=0;i<=M;i++) b[i].x=read();
    int len=1;
    while(len<=N+M) len<<=1;
    fast_fast_tle(len,a,1);
    fast_fast_tle(len,b,1);
    //type为1表示从系数变为点值
    //-1表示从点值变为系数 
    for(int i=0;i<=len;i++) a[i]=a[i]*b[i];
    fast_fast_tle(len,a,-1);
    for(int i=0;i<=N+M;i++) printf("%d ",(int)(a[i].x/len+0.5));//按照我们推倒的公式，这里还要除以n 
    return 0;
}

优化FFT

递归优化

在进行$\text{fft}$时，我们要把各个系数不断分组并放到两侧，那么一个系数原来的位置和最终的位置有什么规律呢？

初始位置：0 1 2 3 4 5 6 7
第一轮后：0 2 4 6|1 3 5 7
第二轮后：0 4|2 6|1 5|3 7
第三轮后：0|4|2|6|1|5|3|7

用|隔开各组数据

我们把二进制拉出来，发现一个位置a上的数，最后所在的位置是a二进制翻转得到的数

那么我们可以据此写出非递归版本$\text{fft}$：先把每个数放到最后的位置上，然后不断向上还原，同时求出点值表示。

蝴蝶操作

貌似也没啥，就是把东西先存上再用，感觉直接看模板就懂了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<cmath>
using namespace std;
const int N=4e6+10;
const double pi=acos(-1.0);
template<typename T>
inline void read(T &x){
    x=0;int f=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) f |= c=='-';
    for(;isdigit(c);c=getchar()) x=x*10+(c^48);
    if(f) x=-x;
}
template<typename T>
inline void write(T x,char ch){
    if(x<0) putchar('-'),x=-x;
    static short st[30],tp;
    do st[++tp]=x%10,x/=10; while(x);
    while(tp) putchar(st[tp--] | 48);
    putchar(ch);
}

int rev[N],b;
struct cp{
    double x,y;
    cp(){x=0,y=0;}
    cp(double xx,double yy){x=xx,y=yy;}
}f[N],g[N],ans[N];
cp operator + (cp a,cp b){return cp(a.x+b.x,a.y+b.y);}
cp operator - (cp a,cp b){return cp(a.x-b.x,a.y-b.y);}
cp operator * (cp a,cp b){return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}                                                                                                  
inline void FFT(int n,cp *a,int type){
    for(int i=0;i<n;i++)
        if(i<rev[i]) swap(a[i],a[rev[i]]);//蝴蝶操作，说实话，我都没看懂哪里来的蝴蝶
    for(int len=1;len<n;len<<=1){
        cp w1(cos(pi/len),sin(pi/len)*type);
        for(int i=0;i<n;i+=(len<<1)){
            cp w(1,0);
            for(int j=0;j<len;j++){
                cp x=a[i+j],y=w*a[i+j+len];
                a[i+j]=x+y; a[i+j+len]=x-y;
                w=w*w1;
            }
        }
    }
}
int n,m,k=1;
int main(){
    read(n),read(m);
    for(int i=0;i<=n;i++) read(f[i].x);
    for(int i=0;i<=m;i++) read(g[i].x);
    while(k<=n+m) k<<=1,b++;
    for(int i=1;i<k;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(b-1));//rev[i]表示i翻转后的值 一个简单DP
    FFT(k,f,1);
    FFT(k,g,1);
    for(int i=0;i<=k;i++) ans[i]=f[i]*g[i];
    FFT(k,ans,-1);
    for(int i=0;i<=n+m;i++) write((int)(ans[i].x/k+0.5),' ');
    return 0;
}

NTT

阶

设 $r,n$ 是互素的整数， $r \not = 0$ ，$n>0$ ，使得 $r^x\equiv 1 \pmod n$ 成立的最小正整数

$x$ 称为 $r$ 模 $x$ 的阶，标为 $\text{ord}_n r$

原根

如果 $r,n$ 都是互素的正整数，当 $\text{ord}_nr=\varphi(n)$ 时，称 $r$ 是模 $n$ 的原根，即 $r$ 是 $n$ 的原根

我们令 $n$ 为大于 $1$ 的 $2$ 的幂，$p$ 为素数且 $n \mid (p-1)$，$g$ 为 $p$ 的一个原根

我们设

$g_n=g^{\frac{p-1}{n}}$

所以

$\begin{eqnarray} g_n^n&=&g^{n·\frac{p-1}{n}}=g^{p-1} \\g_n^{\frac{n}{2}}&=&g^{\frac{g-1}{2}} \\g_{an}^{ak}&=&g^{\frac{ak(p-1)}{an}}=g^{\frac{k(p-1)}{n}}=g_n^k \end{eqnarray}$

我们发现，原根包含着单位根的所有性质，所以我们就可以用原根代替单位根

最大优点：保持精度不变

特殊记忆：998244353的原根是3

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<cmath>
#define int long long
using namespace std;
const int N=4e6+10;
const int mod=998244353;
const int G=3,invG=332748118;
template<typename T>
inline void read(T &x){
    x=0;int f=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) f |= c=='-';
    for(;isdigit(c);c=getchar()) x=x*10+(c^48);
    if(f) x=-x;
}
template<typename T>
inline void write(T x,char ch){
    if(x<0) putchar('-'),x=-x;
    static short st[30],tp;
    do st[++tp]=x%10,x/=10; while(x);
    while(tp) putchar(st[tp--] | 48);
    putchar(ch);
}
inline int power(int x,int k){
	int ans=1;
	while(k){
		if(k&1) ans=ans*x%mod;
		x=x*x%mod;
		k>>=1;
	}
	return ans;
}
int rev[N],b;
int f[N],g[N],ans[N];                                                                                        
inline void FFT(int n,int *a,int type){
    for(int i=0;i<n;i++)
        if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int len=1;len<n;len<<=1){
        int w1=power(type==1?G:invG,(mod-1)/(len<<1));
        for(int i=0;i<n;i+=(len<<1)){
            int w=1;
            for(int j=0;j<len;j++){
                int x=a[i+j]%mod,y=w*a[i+j+len]%mod;
                a[i+j]=(x+y)%mod; a[i+j+len]=(((x-y)%mod)+mod)%mod;
                w=w*w1%mod;
            }
        }
    }
    if(type==1) return ;
    int ny=power(n,mod-2);
    for(int i=0;i<n;i++) a[i]=(a[i]*ny+mod)%mod;
}
int n,m,k=1;
signed main(){
	// system("fc 1.out 1.ans");
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
    read(n),read(m);
    for(int i=0;i<=n;i++) read(f[i]);
    for(int i=0;i<=m;i++) read(g[i]);
    while(k<=n+m) k<<=1,b++;
    for(int i=1;i<k;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(b-1));
    FFT(k,f,1);
    FFT(k,g,1);
    for(int i=0;i<=k;i++) ans[i]=f[i]*g[i]%mod;
    FFT(k,ans,-1);
    for(int i=0;i<=n+m;i++) write(ans[i],' ');
    return 0;
}

多项式乘法逆

题目描述

给定一个多项式 $F(x)$ ，请求出一个多项式 $G(x)$，满足 $F(x)*G(x)\equiv 1\pmod{x^n}$。系数对 $998244353$ 取模。

题解

首先，若 $x$ 只有 $1$ 项时，我们的 $G(x)$ 就是 $x$ 的逆元，不然的话，我们就可以递归求解

我们假设当前已知：

$F(x)*H(x)\equiv1\pmod{x^{\lfloor \frac{n}{2} \rfloor}}$

由于

$F(x)*G(x)\equiv1\pmod {x^n}$

显然：

$F(x)*G(x)\equiv1\pmod {x^{\lfloor \frac{n}{2} \rfloor}}$

两式相减，我们就可以得到：

$F(x)*(G(x)-H(x))\equiv0\pmod{x^{\lfloor \frac{n}{2} \rfloor}}$

左右同时把 $F(x)$ 去掉，则有

$G(x)-H(x)\equiv0\pmod {x^{\lfloor\frac{n}{2}\rfloor}}$

然后我们左右同时平方可以发现：

$(G(x)-H(x))^2\equiv0\pmod{x^{n}}$

拆开后有：

$G^2(x)+H^2(x)-2G(x)H(x)\equiv 0\pmod {x^n}$

再给两边乘上 $F(x)$，化简

$F(x)*(G^2(x)+H^2(x)-2G(x)H(x))\equiv0\pmod{x^n} \\G(x)-2H(x)+F(x)H^2(x)\equiv0 \pmod {x^n} \\G(x)\equiv 2H(x)-F(x)H^2(x) \pmod {x^n} \\G(x) \equiv H(x)\times (2-F(x)H(x)) \pmod {x^n}$

我们发现已经用 $H(x)$ 和 $F(x)$ 来代替 $G(x)$ 了。

然后我们递归去找 $H(x)$ 就行

/*
BlackPink is the Revolution
light up the sky
Blackpink in your area
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<cctype>
#include<bitset>
#include<vector>
#include<map>
#include<set>
#define int long long
using namespace std;
const int N=3e6+5;
const int mod=998244353;
const int G=3,invG=332748118;
typedef long long ll;

namespace scan{
    template <typename T>
    void read(T &x){
        x=0; char c=getchar(); int f=0;
        for(; !isdigit(c); c=getchar()) f |= c=='-';
        for(; isdigit(c); c=getchar()) x = x*10+(c^48);
        if(f) x = -x;
    }

    template <typename T>
    void write(T x,char ch){
        if(x<0) putchar('-'), x = -x;
        static short st[30],tp;
        do st[++tp] = x%10, x/=10; while(x);
        while(tp) putchar(st[tp--] | 48);
        putchar(ch);
    }
}
using namespace scan;
int n,m;
int rev[N];
int a[N],b[N];
int H[N];

inline int qpow(int x,int y){
	int ans=1;
	while(y){
		if(y&1) ans=ans*x%mod;
		x=(x*x)%mod;
		y>>=1;
	}
	return ans;
}

inline void NTT(int n,int *a,int type){
    for(int i=0;i<n;i++)
        if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int len=1;len<n;len<<=1){
        int w1=qpow(type==1 ? G : invG , (mod-1)/(len<<1));
        for(int i=0;i<n;i+=(len<<1)){
            int w=1;
            for(int j=0;j<len;j++){
                int x=a[i+j]%mod,y=w*a[i+j+len]%mod;
                a[i+j]=(x+y)%mod; a[i+j+len]=(((x-y)%mod)+mod)%mod;
                w=w*w1%mod;
            }
        }
    }
    if(type==1) return ;
    int ny=qpow(n,mod-2);
    for(int i=0;i<n;i++) a[i]=(a[i]*ny+mod)%mod;
}

void GetInv(int *F,int *G,int n){
	if(n==1)
		return G[0]=qpow(F[0],mod-2),void();

	GetInv(F,G,(n+1)>>1);
	int len=1,L=0;
	while(len < (n<<1)) len<<=1,L++;
	for(int i=1;i<len;i++) 
		rev[i]=(rev[i>>1] >> 1) | ((i&1) << (L-1));

	for(int i=0;i<n;i++) H[i]=F[i];
	for(int i=n;i<len;i++) H[i]=0;

	NTT(len,H,1); NTT(len,G,1);

	for(int i=0;i<len;i++)
		G[i]=(((2ll-G[i]*H[i]%mod)+mod)%mod*G[i]%mod);
	NTT(len,G,-1);
	for(int i=n;i<len;i++) G[i]=0;
}
signed main(){
    read(n);
    for(int i=0;i<n;i++) read(a[i]),a[i]=(a[i]+mod)%mod;
	GetInv(a,b,n);
	for(int i=0;i<n;i++) write(b[i],' ');
    return 0;
}

多项式对数函数（多项式 ln）

题目描述

给出 $n-1$ 次多项式 $F(x)$ ，求一个 $\bmod x^n$ 下的多项式 $G(x)$，满足 $G(x)\equiv \ln F(x)\pmod {x^n}$

首先，我们令 $f(x)=\ln(x)$

则原式可化为 $G(x)\equiv f(F(x))\pmod{x^n}$

我们对两边同时求导有：

$G’(x) \equiv f’(F(x))F’(x) \pmod {x^{n-1}}$

由于 $\ln’(x)=\dfrac{1}{x}$

$G’(x)\equiv\dfrac{F’(x)}{F(x)} \pmod{x^{n-1}}$

那么我们此时再积回去，得到最终式子

$G(x)=\int \dfrac{F'(x)}{F(x)} \pmod{x^n}$

至于积分和求导的求解，直接看就行

void Direv(int *A,int *B,int len){ //求导
	for(int i=1;i<len;++i) B[i-1]=mul(A[i],i); B[len-1]=0; 
}
void Inter(int *A,int *B,int len){ //积分
	for(int i=1;i<len;++i) B[i]=mul(A[i-1],ksm(i,P-2)); B[0]=0; 
}

void Ln(int *a,int *b,int len){
	Direv(a,A,len),Inv(a,B,len);int l=len<<1;
	NTT(A,1,l),NTT(B,1,l);
	for(int i=0;i<l;++i) A[i]=mul(A[i],B[i]);
	NTT(A,-1,l),Inter(A,b,len);
}

多项式开根

题目描述

给定一个 $n-1$ 次多项式 $A(x)$ ，在 $\bmod x^n$ 意义下的多项式 $B(x)$ ，使得 $B^2(x)\equiv A(x) \pmod {x^n}$。若有多解，请取零次项系数较小的作为答案。

这个和上面那个差不多吧，顶多就是换个推导过程

假设我们已知：

$H^2(x)\equiv F(x) \pmod {x^{\lceil \frac n 2 \rceil}}$

易知：

$G(x)\equiv H(x) \pmod {x^n}$

我们继续推导可得：

$G^2(x)-2H(x)\times G(x)+H^2(x)\equiv 0\pmod{x^n}\\ F(x)-2H(x)\times G(x)+H^2(x)\equiv 0 \pmod{x^n}\\ G(x)\equiv \dfrac{F(x)+H^2(x)}{2H(x)} \pmod {x^n}$

由于题目要求0次项系数最小的最为答案，所以

$G(x)=\dfrac{F(x)+H^2(x)}{2H(x)}$

直接进行多项式求逆和NTT即可

边界：$B_0=\sqrt{A_0}=1$ (二次剩余)

泰勒展开

直接记公式吧：

$G(F)=G\left(F_{0}\right)+G^{\prime}\left(F_{0}\right)\left(F-F_{0}\right)+G^{\prime \prime}\left(F_{0}\right)\left(F-F_{0}\right)^{2}+\cdots$

牛顿迭代

$G(x_0)\equiv G_0(x) \dfrac{F(G_0(x))}{}$

多项式指数函数（多项式 exp）

题目描述

给出 $n-1$ 次多项式 $A(x)$，求一个 $\bmod x^n$ 下的多项式 $B(x)$，满足 $B(x)\equiv e^{A(x)}$。系数对 $998244353$ 取模

查看评论