本文共 6639 字，大约阅读时间需要 22 分钟。

现实打脸时刻

现实：多项式结论的原理都不懂你还听得懂课？

yxy：对…对啊 （pia一耳光，痛

泰勒展开

考虑一个函数 $f(x)$ ，他的值随着自变量 $x$ 改变而改变

在 $x=x_0$ 处展开即为：

$$f(x)=\sum _{i=0}^{\infty }\frac{f^{(i)}(x_0)}{i!}(x-x_0{)}^i$$

证明：

若函数 $f(x)=g(x)$ 成立，当且仅当在 $x_0$ 处时，$f(x_0)=g(x_0)$ 且 $f^{(n)}(x_0)=g^{(n)}(x_0)$ ，（$n$ 可以是任意正整数）。然后你会发现上面那个式子左右两边不管取多少次导在 $x_0$ 处都相等。这样就非常不严谨地证明了泰勒展开的公式。

$f(x)={\sum }_{i=0}^{\infty }\frac{f^{(i)}(x_0)}{i!}(x-x_0{)}^i$ 这个等式就是 $f(x)$ 在 $x_0$ 处的泰勒展开式；右边的式子 ${\sum }_{i=0}^{\infty }\frac{f^{(i)}(x_0)}{i!}(x-x_0{)}^i$ 称为 $f(x)$ 在 $a$ 处的泰勒级数。 麦克劳林级数就是函数在 $x=0$ 处展开的泰勒级数。

并不是 $f(x)$ 定义域内的所有 $x$ 都可以展开，因为不是函数的每个位置都是可导的。但是在多项式上，我们的 $x$ 的数域是形式幂级数，那么就不存在这个问题了

牛顿迭代

求一个关于 $x$ 的多项式 $F(x)$，使得对于一给定的关于 $F(x)$ 的函数 $G(F(x))$，$G(F(x))\equiv 0(mod{x}^n)$ 成立。

多项式函数 $G(F(x))$，他的值随着自变量 $F(x)$ 的的改变而改变

在 $F(x)=F_0(x)$ 处展开即为：

$$G(F(x))=\sum _{i=0}^{\infty }\frac{G^{(i)}(F_0(x))}{i!}{(F(x)-F_0(x))}^i$$

现在要求 $F(x)$ 满足 $G(F(x))\equiv 0(mod{x}^n)$

设我们已经求出了在摸 $x^{\lceil \frac{n}{2}\rceil }$ 下的根 $F_0(x)$ ，将 $G(F(x))$ 在 $F_0(x)$ 处泰勒展开

$$G(F(x))=\sum _{i=0}^{\infty }\frac{G^{(i)}(F_0(x))}{i!}{(F(x)-F_0(x))}^i\equiv 0(mod{x}^n)$$

将 $F(x)=x^{\lceil \frac{n}{2}\rceil }H(x)+F_0(x)$ 代入上式
$$\begin{gathered} \sum _{i=0}^{\infty }\frac{G^{(i)}(F_0(x))}{i!}{(x^{\lceil \frac{n}{2}\rceil }H(x)+F_0(x)-F_0(x))}^i\equiv 0(mod{x}^n) \\ \sum _{i=0}^{\infty }\frac{G^{(i)}(F_0(x))}{i!}{(x^{\lceil \frac{n}{2}\rceil }H(x))}^i\equiv 0(mod{x}^n) \end{gathered}$$
对于 ${(x^{\lceil \frac{n}{2}\rceil }H(x))}^i$ ，当 $i\ge 2$ 时 ${(x^{\lceil \frac{n}{2}\rceil }H(x))}^i\equiv 0(mod{x}^n)$ 。因此这里在模意义下的泰勒级数，从第三项开始全部为 $0$，那么只保留前两项，即：
$$\begin{gathered} \sum _{i=0}^{\infty }\frac{G^{(i)}(F_0(x))}{i!}{(x^{\lceil \frac{n}{2}\rceil }H(x))}^i\equiv G(F_0(x))+G^{\prime }(F_0(x))\cdot (x^{\lceil \frac{n}{2}\rceil }\cdot H(x))\equiv 0(mod{x}^n) \\ H(x)\equiv -x^{-\lceil \frac{n}{2}\rceil }\frac{G(F_0(x))}{G^{\prime }(F_0(x))}(mod{x}^n) \\ F(x)\equiv F_0(x)-\frac{G(F_0(x))}{G^{\prime }(F_0(x))}(mod{x}^n) \end{gathered}$$
总结：牛顿迭代可以用于求解 $G(F(x))$ 在模 $x^n$ 意义下的根，可以运用于多项式求逆，多项式开根，多项式exp。牛顿迭代只是泰勒展开的一个延伸，为什么每次精度倍增还是要看本质泰勒展开。一些题还是只能用泰勒展开，当然能用牛迭还是用他因为他方便嘛。

//多项式求逆,ln,exp//RA100FDM#include <bits/stdc++.h>#define N 400005using namespace std;typedef long long ll; typedef vector<ll> vec;const ll mod=998244353;int now_limit;int rev[N];ll wq[20][N],fac[N],inv[N];ll ksm(ll x,ll y){   	ll res=1; while(y){    if(y&1)res=res*x%mod; x=x*x%mod; y>>=1; }	return res;}void init_NTT(int limit){   	if(limit==now_limit) return;	now_limit=limit; int l=0; while((1<<l)<limit)l++;	for(int i=0;i<limit;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));	if(wq[0][0]==0){   		for(int mid=1,l=0;mid<N;mid<<=1,l++){   			wq[l][0]=1,wq[l][1]=ksm(3,(mod-1)/(mid<<1));			for(int k=2;k<mid;k++) wq[l][k]=wq[l][k-1]*wq[l][1]%mod;		}	}}void NTT(vec &a,int limit,int flag){   	init_NTT(limit);	while(a.size()<limit) a.push_back(0);	for(int i=0;i<limit;i++) if(i<rev[i])swap(a[i],a[rev[i]]);	ll x,y;	for(int mid=1,l=0;mid<limit;mid<<=1,l++)		for(int j=0;j<limit;j+=(mid<<1))			for(int k=0;k<mid;k++){   				x=a[j+k],y=a[j+k+mid]*wq[l][k]%mod;				a[j+k]=(x+y)%mod,a[j+k+mid]=(x-y+mod)%mod;			}	if(flag==-1){   		x=ksm(limit,mod-2);		for(int i=0;i<limit;i++) a[i]=a[i]*x%mod;		reverse(&a[1],&a[limit]);	}}void init_Ln(){   	fac[0]=1;	for(ll i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;	inv[N-1]=ksm(fac[N-1],mod-2);	for(ll i=N-1;i>0;i--) inv[i-1]=inv[i]*i%mod,inv[i]=inv[i]*fac[i-1]%mod;}struct poly{   	vec s;	poly(int len=-1){    s.resize(len+1); }	poly Inv(int len){   		if(len==1){   			poly b; 			b.s.push_back(ksm(s[0],mod-2)); b.s.push_back(0); 			return b;		}		poly b=Inv((len+1)>>1),c; 		c.s=vector<ll>(&s[0],&s[len]);		int limit=1; while(limit<(len<<1)) limit<<=1;		NTT(b.s,limit,1),NTT(c.s,limit,1);		for(int i=0;i<limit;i++) b.s[i]=(mod+2ll-c.s[i]*b.s[i]%mod)%mod*b.s[i]%mod;		NTT(b.s,limit,-1);		for(int i=len;i<b.s.size();i++)b.s[i]=0;		return b;	}	poly Ln(int len){   		if(!fac[0]) init_Ln();		poly b,c=Inv(len);		b.s=vector<ll>(&s[0],&s[len]);		for(ll i=0;i<len-1;i++) b.s[i]=b.s[i+1]*(i+1)%mod; b.s[len-1]=0;//		int limit=1; while(limit<(len<<1)) limit<<=1;		NTT(c.s,limit,1),NTT(b.s,limit,1);		for(int i=0;i<limit;i++) b.s[i]=b.s[i]*c.s[i]%mod;		NTT(b.s,limit,-1);		for(int i=len-1;i>=1;i--) b.s[i]=b.s[i-1]*inv[i]%mod; b.s[0]=0;		for(int i=len;i<b.s.size();i++) b.s[i]=0;		return b;	}	poly Exp(int len){   		if(len==1){   			poly b;			b.s.push_back(1),b.s.push_back(0); 			return b; 		}		poly b=Exp((len+1)>>1); 		poly c=b.Ln(len); c.s[0]=(1-c.s[0]+s[0]+mod)%mod;		for(int i=1;i<len;i++) c.s[i]=(s[i]-c.s[i]+mod)%mod;		int limit=1; while(limit<(len<<1))limit<<=1;		NTT(b.s,limit,1),NTT(c.s,limit,1);		for(int i=0;i<limit;i++) b.s[i]=b.s[i]*c.s[i]%mod;		NTT(b.s,limit,-1);		for(int i=len;i<b.s.size();i++) b.s[i]=0;		return b;	}}; int main(){   	int len;	poly a; cin>>len;	int v;	for(int i=0;i<len;i++)		scanf("%d",&v),a.s.push_back(v);	a=a.Exp(len);	for(int i=0;i<len;i++) cout<<a.s[i]<<' ';}