多项式全家桶

导数公式

\((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})\)

复合函数求导：

\(f(g(x))^{'} =f^{'}(g(x))g^{'}(x)\)

对于多个函数的也类似就是这样

\(f(g(h(x)))^{'}=f^{'}(g(h(x)))g^{'}(h(x))h^{'}(x)\)

我一般记忆成内部不变 ，外部一层一层展开并求导

---

快速傅里叶变换（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}\)

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

计算：平行四边形法则(其实就是分配律)，注意这里的 \(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\)次单位根

单位根的性质与反演

单位根的性质：

1. \(\omega _n ^k =\cos~k\dfrac{2\pi}{n}+i\times \sin~k\dfrac{2\pi}{n}\)
2. \(\omega _{2n}^{2k}=\omega _n^k\)
3. \(\omega_n^{k+\frac{n}{2}}=-\omega _n^k\)
4. \(\omega_n^0=\omega _n^n=1\)
5. \((\omega _n^k)^2=\omega_n^{2k}\)

第二条的证明：

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

约分后就和原来一样了

第三条的证明：

\[\begin{aligned} \omega_n^{k+\frac n 2} &= \cos (k+\dfrac n 2) \dfrac {2\pi} n + i\times\sin (k+\dfrac n 2) \dfrac {2\pi} n\\ &=\cos (k\dfrac {2\pi} n +\pi)+i\times \sin (k \dfrac {2\pi} n + \pi)\\ &=\cos k\dfrac {2\pi} n\cos \pi - \sin k\dfrac {2\pi} n\sin \pi+i\times(\sin k \dfrac {2\pi}{n} \cos \pi +\cos k\dfrac{2\pi}{n}\sin\pi)\\ &=-\cos k\dfrac {2\pi} n-0+i\times (-\sin k \dfrac {2\pi} n + 0)\\ &=-\omega_{n}^{k} \end{aligned} \]

单位根反演：

\[\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 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^{-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)\) 的各项系数

离散傅里叶变换（DFT）的数学证明

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

\[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) \\&=&A_1(\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\dots\omega_{\frac n 2} ^{\frac n 2}\) 等的点值表示，就可以 \(O(n)\) 的求出 \(A(\omega_n^{1\sim\frac n 2})\) 的点值表示，同时可以得到 \(A(\omega_n^{\frac n2 + 1\sim n})\)，正好 \(n\) 个，每个 \(A_1\) 和 \(A_2\) 也这么求，持续分治，分治的边界是 \(n=1\)

另外一边我们是离散傅里叶逆变换(IDFT) 也就这么理解就行了

#include
#include
#include
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二进制翻转得到的数

那么我们可以据此写出非递归版本 \(\mathrm{FFT}\)：先把每个数放到最后的位置上，然后不断向上还原，我们每次把相邻的两块共同贡献给上面的那一块，同时求出点值表示。

蝴蝶操作

貌似也没啥，就是把东西先存上再用，感觉直接看模板就懂了，差不多得了，还是直接背吧

/*
BlackPink is the Revolution
light up the sky
Blackpink in your area
*/
const int mod = 1e9 + 7;
const int N = 3e6 + 5;
const double Pi = acos(-1.0);
int n, m, T, L, lim, rev[N];
struct cp {
	double x, y;
	cp() {x = 0, y = 0;}
	cp(double a, double b) {x = a, y = b;}
}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(cp *a, int type) {
	rep (i, 0, lim - 1) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int len = 1; len < lim; len <<= 1) {
		cp wn(cos(Pi / len), sin(Pi / len) * type);
		for (int i = 0; i < lim; i += (len << 1)) {
			cp w(1, 0), x, y;
			rep (j, 0, len - 1) {
				x = a[i + j], y = w * a[i + j + len];
				a[i + j] = x + y, a[i + j + len] = x - y;
				w = w * wn;
			}
		}
	}
}

int main(){
	read(n, m);
	for (lim = 1; lim <= n + m; lim <<= 1) L++;
	rep (i, 0, n) read(f[i].x);
	rep (i, 0, m) read(g[i].x);
	rep (i, 0, lim - 1) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
	FFT(f, 1);
	FFT(g, 1);
	rep (i, 0, lim) ans[i] = f[i] * g[i];
	FFT(ans, -1);
	rep (i, 0, n + m) write((int)(ans[i].x / lim + 0.5), ' ');
	return 0;
}
//write:RevolutionBP

---

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\)

/*
BlackPink is the Revolution
light up the sky
Blackpink in your area
*/
const int mod = 998244353;
const int N = 5e6 + 5;
const int G = 114514;
const double Pi = acos(-1.0);
#define int long long

int n, m, T, b, lim, rev[N], f[N], g[N], ans[N];
const int invG = power(G, mod - 2);
inline void FFT(int *a, int type) {
	rep (i, 0, lim - 1) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int len = 1; len < lim; len <<= 1) {
		int wn = power(type == 1 ? G : invG, (mod - 1) / (len << 1));
		for (int i = 0; i < lim; i += (len << 1)) {
			int w = 1, x, y;
			rep (j, 0, len - 1) {
				x = a[i + j], y = 1ll * w * a[i + j + len] % mod;
				a[i + j] = (x + y) % mod, a[i + j + len] = (x - y + mod) % mod;
				w = 1ll * w * wn % mod;
			}
		}
	}
    if (type == 1) return ;
    int inv = power(lim, mod - 2);
    rep (i, 0, lim) a[i] = a[i] * inv % mod;
}

signed main(){
	read(n, m);
	for (lim = 1; lim <= n + m; lim <<= 1);
	rep (i, 0, n) read(f[i]);
	rep (i, 0, m) read(g[i]);
	rep (i, 0, lim - 1) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (lim >> 1));
	FFT(f, 1), FFT(g, 1);
	rep (i, 0, lim) ans[i] = f[i] * g[i];   
	FFT(ans, -1);
	rep (i, 0, n + m) write(ans[i], ' ');
	return 0;
}
//write:RevolutionBP

---

多项式乘法逆

题目描述

给定一个多项式 \(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)\) 就行

inline void Inv(ll *X, ll *Y, ll len) {
    if (len == 1) return Y[0] = inv(X[0]), void();
    Inv(X, Y, (len + 1) >> 1);
    for (lim = 1; lim < (len << 1); lim <<= 1);
    static ll H[N];
    rep (i, 0, len - 1) H[i] = X[i];
    rep (i, len, lim - 1) H[i] = 0;
    NTT(H, 1, lim), NTT(Y, 1, lim);
    rep (i, 0, lim)
        Y[i] = ((2ll - Y[i] * H[i] % mod) + mod) % mod * Y[i] % mod;
    NTT(Y, -1, lim);
    rep (i, len, lim - 1) Y[i] = 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} \]

至于积分和求导的求解，直接看就行
求导公式 $$\displaystyle x^{a'}=ax{a-1}$$

积分公式$$\displaystyle \int x^{adx=\frac{1}{a+1}x}{a+1}$$

void Direv(int *A,int *B,int len){ //求导
	for(int i=1;i

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

---

多项式开根

题目描述

给定一个 \(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即可

t{A_0}=1$

---

泰勒展开

看了知乎上一个回答，倒是蛮有趣的

首先对于这个函数，我们定义它为 \(f(x)\)

我们现在想做的就是构造一个函数 \(g(x)\) 和它亿分相似

首先我们就要找一个点和它重合，哪个点呢？显然 \((0,1)\) 是最好的选择

然后我们就会选择在 \((0,1)\) 处进行 \(n\) 阶求导，然后找到一个函数 \(g(x)\) 使得这 \(p(p\in [1,n])\) 阶的导数全部和 \(f(x)\) 的 \(p\) 阶导数相同，然后我们会考虑，可能一次两次的，我们愿意算，但是太多了肯定就不愿意了，所以这个 \(g(x)\) 得长得靠谱，还得好算

所以我们有了一个绝妙的主意，我们用多项式来代替，众嗦粥之，众所周知，我们的 \(n\) 次多项式 \(n\) 阶求导以后可是个常数啊，这一点就会非常好用

这里的图引自知乎，第一条回答（号主已经把号注销了，所以我也没法确认，如有侵权希望可以和我私聊）

满足二阶导数时，我们的图长这样

满足四阶导数时，我们的图长这样

很容易想到，如果我们的函数无穷次求导以后，这两个函数就会无限接近

比如说我们要求 \(\cos 2\)，这很难求，但是我们肯定知道 \(\cos \dfrac \pi 2\) 的值，那么直接进行一个很多次的求导，然后在我的构造函数上就能找到近似值

那么我们考虑能不能直接用代数式子直接推出来呢？

答案是肯定的，刚才我们说，如果我们 \(n\) 次求导以后两个函数会无限相似

首先容易得到，如果我们是 \(n\) 次求导，那么最后我们得到的式子长这样

\[g(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots a_nx^n \]

首先容易得到 \(a_0=g(0)=f(0)\)

当 \(g^n(x)\) 时，原式长成 \(n!a_n\)。

容易得到： \(g^n(0)=f^n(0)=n!a_n\)

所以

\[a_n=\dfrac {f^n(0)} {n!} \]

综上：

\[g(x)=g(0)+\frac{f^{1}(0)}{1!}x+\frac{f^{2}(0)}{2!}x^{2}+……+\frac{f^{n}(0)}{n!}x^{n} \]

若我们不是从 \((0,f(0))\) 开始的，而是从 \((x_0,f(x_0))\) 开始的，那么这个式子改一改就有了

\[f(x)\approx g(x)=g(x_{0})+\frac{f^{1}(x_{0})}{1!}(x-x_{0})+\frac{f^{2}(x_{0})}{2!}(x-x_{0})^{2}+……+\frac{f^{n}(x_{0})}{n!}(x-x_{0})^{n} \]

在 \(\mathrm{OI}\) 中，我们很多东西都是有精度限制的，请问我们这个式子什么时候才能算到我们要的误差之内呢？

首先我们发现，我们的式子是越来越小的，原因我们可以这样理解

泰勒展开是先把函数的大框架构建完毕，然后精细化的过程，所以你后面的是基于前面的框架搭建的所以是越来越小，越来越精细的过程

我们会发现，其实我们的式子可远不止这些，我们后面的式子可以无限拉长，类似这样：

\[f(x)\approx g(x)=g(x_{0})+\frac{f^{1}(x_{0})}{1!}(x-x_{0})+\frac{f^{2}(x_{0})}{2!}(x-x_{0})^{2}+…+\frac{f^{n}(x_{0})}{n!}(x-x_{0})^{n}+\dfrac {f^{n+1}(x_0)} {(n+1)!}(x-x_0)^{n+1}+\dots+\dfrac {f^{\infin}(x_0)} {\infin!}(x-x_0)^{\infin} \]

假设现在我们把 \(g\) 精确到 \(n\) 阶了， 那么后面的那一堆就是误差项，有一个叫佩亚诺的倒霉蛋试着去化简这个误差项，结果后来啥也没搞出来，不过他用后面的和前面做了个商，算出来了一个东西，不够为了纪念他，我们还是将这个误差项叫作佩亚诺余项

他算了个这玩意：

\[\dfrac {\huge{误差项}} {泰勒展开的第~n~项}=\dfrac {f^{n+1}(x_0)} {(n+1)f^n(x_0)}(x-x_0)+\dfrac {f^{n+2}(x_0)} {(n+1)f^n(x_0)}(x-x_0)^2+\cdots \]

然后就是两位天才的故事拉格朗日和柯西

首先是一个简单的问题，给你一段时间内汽车走过的路程与时间的关系（\(ST\) 图像），然后我告诉你平均速度是 \(v_1\)，然后还告诉你其中某一点的速度是 \(v_0，那么我们很容易知道一定会出现一个点的速度 \(v_2\) 使得 \(v_2>v_1\)

然后这个叫拉格朗日的神仙就直接把这个写成了一个方程，我们称其为拉格朗日中值定理：

\[\dfrac {S(t_2)-S(t_1)} {t_2-t_1}=S^{'}(t^{'}) ~~~~~~~~~~t^{'} \in (t1,t2) \]

然后柯西拓展了一下，变成了柯西中值定理

\[\frac{S(t_{2})-S(t_{1})}{T(t_{2})-T(t_{1})}=\frac{S^{'}(t^{'})}{T^{'}(t^{'})} ~~~~~~~~~~t^{'} \in (t1,t2) \]

然后我们回归原来我们的误差项等一系列定义

\[R(x)=\dfrac {f^{n+1}(x_0)} {(n+1)!}(x-x_0)^{n+1}+\dots+\dfrac {f^{\infin}(x_0)} {\infin!}(x-x_0)^{\infin} \]

我们设 \(T(x)=(x-x_0)^{n+1}\)，且 \(T(x_0)=R(x_0)=0\)

我们让等式两边同时除以 \(T(x)\)，并且使用柯西中值定理，有

\[\dfrac {R(x)} {T(x)}=\dfrac {R(x)-0} {T(x)-0}=\dfrac {R(x)-R(x_0)} {T(X)-T(x_0)}=\dfrac {R^{'} (\xi)} {T^{'}(\xi)}=\dfrac {R^{'} (\xi)} {(n+1)(\xi-x_0)^n} \]

然后我们很容易发现，我们仿照刚才的方式容易得到，上面的那个玩意可以无穷次求导，并且长得和我们刚才的 \(R(x)\) 除了每一项前面加了个系数 \((n+y)\) 以外都一样，下面的话也是，并且下面除去 \((n+1)\) 以外也一样，分开写出来

分子：

\[R(x)=\dfrac {f^{n+1}(x_0)} {(n+1)!}(x-x_0)^{n+1}+\dots+\dfrac {f^{\infin}(x_0)} {\infin!}(x-x_0)^{\infin} \]

所以

\[R^{'}(x)=(n+1)\dfrac {f^{n+1}(x_0)} {(n+1)!}(\xi-x_0)^{n}+(n+2)\dfrac {f^{n+2}(x_0)} {(n+2)!}(\xi-x_0)^{n+1}+\dots+\dfrac {f^{\infin}(x_0)} {\infin!}(\xi-x_0)^{\infin} \]

于是我们可以设 \(P(\xi)=R^{'}(\xi)\) 且 \(P(x_0)=0\)

分母：

我们可以直接设 \(Q(\xi)=T^{'}(\xi)\)，且 \(Q(x_0)=0\)

发现原式变成了 \(\dfrac {P(\xi)} {Q(\xi)}\)，很巧合我们可以继续用柯西中值定理归纳

很容易发现我们可以一直这样归纳最终的结果就会是

\[{误差项}=\frac{f^{n+1}(\xi)}{(n+1)!}(x-x_{0})^{n+1} \]

这样的话就非常非常非常好了，我们不用让 \(x\) 趋近于 \(x_0\)，直接就能算出一个点的误差值

老实说，后面的这一堆东西我们一般也就数学分析的时候用，OI中还是泰勒展开直接应用比较多，原因是生成函数等对于 \(x^n\) 是无效的，所以我们不用考虑这么多，直接套公式使用即可

---

牛顿迭代

牛顿迭代就是说，我们给定一个连续的函数 \(f(x)\)，然后我们随便找它上面的一个点，然后作切线，发现这个切线会和 \(x\) 轴有一个交点，然后我们以这个交点作垂线，交函数上一个点，然后 继续上述操作，我们最终会发现我们的这个和 \(x\) 轴的交点会无限逼近 \(f(x)\) 和 \(x\) 轴的交点

代数方法说明的话就是我们设刚开始函数上这个交点是 \((x_n,f(x_n))\)，那么和 \(x\) 轴交在了 \((x_{n+1},0)\)。我们重复这个过程，如下图

而且我们顺带说一下切线方程：我们如果已知 \(f(x)=kx+b\)，那么我们的 \(k\) 可以用导数表示出来，即 \(f(x)=f^{'}(x)+b\) 我们称其为切线方程，对于刚才这个玩意我们也可以用类似这种方式解决，我们要求 \(x_{n+1}\) 的值，即求 $f(x_n)+f^{'}(x_n)\times(x_{n+1}-x_n)=0 $，我们搞一搞：

\[x_{n+1}=x_n-\dfrac {f(x_n)} {f^{'}(x_{n})} \]

同理我们把横坐标及函数转化成多项式形式，就有 ：

\[G(x_0)\equiv G_0(x)-\dfrac{F(G_0(x))}{F^{'}(G_0(x))} \]

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

题目描述

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

首先对于两边同时取 \(\ln\)，没什么好说的

\[\ln B(x)\equiv A(x)\pmod {x^n} \]

我们令 \(F(G(x))=\ln B(x)- A(x)\equiv 0\pmod {x^n}\)

并且我们容易得到：

\[F^{'}(G(x)) = \dfrac {1} {G(x)} \]

代入牛顿迭代以后得到：

\[G(x)\equiv G_0(x)-\dfrac {\ln G_0(x)-F(x)} {\frac 1 {G(x)}}\pmod {x^n} \]

化简后得：

\[G(x)\equiv G_0(x)(1-\ln G_0(x)+F(x)) \pmod {x^n} \]

---

到这里，最简单的多项式已经都有了，剩下的也是这些的拓展和加深，所以我们可以放出vector封装好的多项式模板了

/*
Blackpink is the Revolution
light up the sky
Blackpink in your area
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include