也许更好的阅读体验

前置知识

FFT
牛顿迭代
求导

定义

简单来说，形如 $a_0{x}^0+a_1{x}^1+a_2{x}^2+\cdots +a_n{x}^n$a0​x0+a1​x1+a2​x2+⋯+an​xn，的代数表达式叫做多项式
可以记作 $f\left(x\right)=a_0{x}^0+a_1{x}^1+a_2{x}^2+\cdots +a_n{x}^n$f(x)=a0​x0+a1​x1+a2​x2+⋯+an​xn
其中 a0​,a1​,⋯,an​叫做多项式的系数， $x$x是一个不定元，不表示任何值
不定元在多项式中最大项的次数称作多项式的次数

多项式的表示法

系数表示法

像刚刚我们提到的那些多项式，都是以系数形式表示的，也就是将 $n$n次多项式 $f\left(x\right)$f(x)的系数 a0​,a1​,⋯,an​看作 $n+1$n+1维向量 a =(a0​,a1​,⋯,an​)，其系数表示就是向量 $\overrightarrow{a}$a

点值表示法

如果 $n+1$n+1个不同的数 x0​,x1​,⋯,xn​对多项式进行求值，得到 f(x0​),f(x1​),⋯,f(xn​)，那么就称 $\{(x_i,f\left(x_i\right))\mid 0\le i\le n,i\in Z\}${(xi​,f(xi​))∣0≤i≤n,i∈Z}为多项式 $f\left(x\right)$f(x)的点值表示
注意， $n+1$n+1个点值只能表示 $n$n次多项式

多项式的基本运算

两个多项式 $\begin{array}{c}{\displaystyle f\left(x\right)=\sum _{i=0}^{\infty }{a}_i{x}^i}\end{array}$f(x)=i=0∑∞​ai​xi​， $\begin{array}{c}{\displaystyle g\left(x\right)=\sum _{i=0}^{\infty }{b}_i{x}^i}\end{array}$g(x)=i=0∑∞​bi​xi​

加法

$\begin{array}{c}{\displaystyle h\left(x\right)=f\left(x\right)+g\left(x\right)=\sum _{i=0}^{\infty }(a_i+b_i)x^i}\end{array}$h(x)=f(x)+g(x)=i=0∑∞​(ai​+bi​)xi​

乘法

$\begin{array}{c}{\displaystyle f\left(x\right)=f\left(x\right)\ast g\left(x\right)=\sum _{i=0}^{\infty }\sum _{j+k=i}(a_j\cdot b_k)x^i}\end{array}$f(x)=f(x)∗g(x)=i=0∑∞​j+k=i∑​(aj​⋅bk​)xi​

多项式的其它运算

基本套路

从现在开始要用到牛顿迭代了
一般基本套路是运用牛顿迭代倍增求解

1. 先构造一个复合多项式 $g$g，使 $g\left(f\right)=0$g(f)=0
2. 对 $g$g求导
3. 牛顿迭代

为了方便阅读，下面把牛顿迭代再贴一次

$f\equiv f_0-\frac{g\left(f_0\right)}{g^{\prime }\left(f_0\right)}\left(mod{x}^{2n}\right)$f≡f0​−g′(f0​)g(f0​)​( mod x2n)

有一个多项式 $A$A

多项式求逆

设 $f=\frac{1}{A}$f=A1​，求 $f$f的前 $n$n项

构造 $g\left(f\right)=\frac{1}{f}-A=0$g(f)=f1​−A=0，我们知道 $f$f的常数项为 $A$A的常数项的逆元，接下来开始迭代
此时有 $g^{\prime }\left(f_0\right)=-\frac{1}{f_0^2}$g′(f0​)=−f02​1​

$g^{\prime }\left(f_0\right)=(f_0^{-1}-A{)}^{\prime }$g′(f0​)=(f0−1​−A)′，将 $A$A看为常数项
$g^{\prime }\left(f_0\right)=(f_0^{-1}-A{)}^{\prime }=-f_0^{-2}=-\frac{1}{f_0^2}$g′(f0​)=(f0−1​−A)′=−f0−2​=−f02​1​

根据牛顿迭代
有 $f\equiv f_0-\frac{\frac{1}{f_0}-A}{-\frac{1}{f_0^2}}\left(mod{x}^{2n}\right)\equiv 2f_0-A{f}_0^2\left(mod{x}^{2n}\right)$f≡f0​−−f02​1​f0​1​−A​( mod x2n)≡2f0​−Af02​( mod x2n)
至此，我们推完了，拿出来，写在下面

$f\equiv 2f_0-A{f}_0^2\left(mod{x}^{2n}\right)$f≡2f0​−Af02​( mod x2n)

现在我们可以由 $f_0$f0​去推 $f$f，每次这个模数 $x^y$xy的 $y$y会乘以2，也就是说是倍增的
初始时 $n=1$n=1
时间复杂度 $O\left(nlogn\right)$O(nlogn)

多项式求ln

求 $f=lng$f=ln g的前 $n$n项
我们对其求导
$f^{\prime }\left(x\right)=\frac{g^{\prime }\left(x\right)}{g\left(x\right)}$f′(x)=g(x)g′(x)​

复合求导
ln -> u
g -> v

这样，我们只要对 $g$g求逆，然后对 $g$g求导得 $g^{\prime }$g′，之后我们就得到了 $f^{\prime }$f′，再对其积分得到 $f$f
求导和积分都是 $O\left(n\right)$O(n)的
时间复杂度 $O\left(nlogn\right)$O(nlogn)

多项式exp

求 $f=e^A$f=eA ( $A$A的常数项为 $0$0)的前 $n$n项

构造 $g\left(f\right)=lnf-A$g(f)=ln f−A
我们知道 $f$f的常数项为 $1$1
对 $g$g求导， $g^{\prime }\left(f_0\right)=\frac{1}{f_0}$g′(f0​)=f0​1​
根据牛顿迭代
$\begin{array}{cc}{\displaystyle f}& {\displaystyle \equiv f-\frac{ln{f}_0-A}{\frac{1}{f_0}}\left(mod{x}^{2n}\right)}\\ {\displaystyle }& {\displaystyle \equiv f_0(1-\ln f_0+A)\left(mod{x}^{2n}\right)}\end{array}$f​≡f−f0​1​lnf0​−A​( mod x2n)≡f0​(1−lnf0​+A)( mod x2n)​

至此，我们推完了，拿出来，写在下面

$f\equiv f_0(1-\ln f_0+A)\left(mod{x}^{2n}\right)$f≡f0​(1−lnf0​+A)( mod x2n)

还是倍增
求 $ln$ln和多项式乘法都是 $O\left(nlogn\right)$O(nlogn)的，加法是 $O\left(n\right)$O(n)的
时间复杂度 $O\left(nlogn\right)$O(nlogn)

多项式开方

求 $f=\sqrt{A}$f=A ​ ( $A$A的常数项存在平方根)的前 $n$n项

构造 $g\left(f\right)=f^2-A$g(f)=f2−A
我们知道 $f$f的常数项为 $A$A常数项的平方根
可用二次剩余方法解
对 $g$g求导 $g^{\prime }\left(f_0\right)=2f_0$g′(f0​)=2f0​
根据牛顿迭代
$f\equiv f_0-\frac{f_0^2-A}{2f_0}\left(mod{x}^{2n}\right)$f≡f0​−2f0​f02​−A​( mod x2n)
时间复杂度 $O\left(nlogn\right)$O(nlogn)

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧
如能得到推荐博主就更开心了
您的鼓励是博主的动力