前置知识
定义
简单来说，形如(a_0x^0+a_1x^1+a_2x^2+cdots+a_nx^n)，的代数表达式叫做多项式
可以记作(f(x)=a_0x^0+a_1x^1+a_2x^2+ cdots+a_nx^n)
其中(a_0,a_1,cdots,a_n)叫做多项式的系数，(x)是一个不定元，不表示任何值
不定元在多项式中最大项的次数称作多项式的次数
多项式的表示法
系数表示法
像刚刚我们提到的那些多项式，都是以系数形式表示的，也就是将(n)次多项式(f(x))的系数(a_0,a_1,cdots,a_n)看作(n+1)维向量(overrightarrow{a}=(a_0,a_1,cdots,a_n))，其系数表示就是向量(overrightarrow{a})
点值表示法
如果(n+1)个不同的数(x_0,x_1,cdots,x_n)对多项式进行求值，得到(f(x_0),f(x_1),cdots,f(x_n))，那么就称(left{ left( x_{i},fleft( x_{i}
ight)
ight)|0leq ileq n,iin Z
ight})为多项式(f(x))的点值表示
注意，(n+1)个点值只能表示(n)次多项式
多项式的基本运算
两个多项式(egin{aligned}f(x)=sum_{i=0}^{infty}a_ix^iend{aligned})，(egin{aligned}g(x)=sum_{i=0}^{infty}b_ix^iend{aligned})
加法
(egin{aligned}h(x)=f(x)+g(x)=sum_{i=0}^{infty}(a_i+b_i)x^iend{aligned})
乘法
(egin{aligned}f(x)=f(x)*g(x)=sum_{i=0}^{infty}sum_{j+k=i} (a_jcdot b_k)x^iend{aligned})
多项式的其它运算
基本套路
从现在开始要用到牛顿迭代了
一般基本套路是运用牛顿迭代倍增求解
- 先构造一个复合多项式(g)，使(g(f)=0)
- 对(g)求导
- 牛顿迭代
为了方便阅读，下面把牛顿迭代再贴一次
(fequiv f_{0}-dfrac {gleft( f_{0} ight) }{g'left( f_{0} ight) }left( mod x^{2n} ight))
有一个多项式(A)
多项式求逆
设(f=dfrac{1}{A})，求(f)的前(n)项
构造(gleft( f
ight) =dfrac {1}{f}-A=0)，我们知道(f)的常数项为(A)的常数项的逆元，接下来开始迭代
此时有 (g'(f_0)=-dfrac{1}{f_0^2})
(g'(f_0)=(f_0^{-1}-A)')，将(A)看为常数项
(g'(f_0)=(f_0^{-1}-A)'=-f^{-2}_0=-dfrac{1}{f_0^2})
根据牛顿迭代
有(fequiv f_0-dfrac{dfrac{1}{f_0}-A}{-dfrac{1}{f_0^2}}left( mod x^{2n}
ight)equiv2f_0-Af_0^2left( mod x^{2n}
ight))
至此，我们推完了，拿出来，写在下面
(fequiv2f_0-Af_0^2left( mod x^{2n} ight))
现在我们可以由(f_0)去推(f)，每次这个模数(x^y)的(y)会乘以2，也就是说是倍增的
初始时(n=1)
时间复杂度(O(nlogn))
多项式求ln
求(f=ln g)的前(n)项
我们对其求导
(f'left( x
ight) =dfrac {g'(x)}{gleft( x
ight) })
复合求导
ln -> u
g -> v
这样，我们只要对(g)求逆，然后对(g)求导得(g')，之后我们就得到了(f')，再对其积分得到(f)
求导和积分都是(O(n))的
时间复杂度(O(nlogn))
多项式exp
求(f=e^A) ((A)的常数项为(0))的前(n)项
构造(g(f)=ln f-A)
我们知道(f)的常数项为(1)
对(g)求导，(g'(f_0)=dfrac{1}{f_0})
根据牛顿迭代
(egin{aligned}f&equiv f-dfrac {lnf_{0}-A}{dfrac {1}{f_{0}}}left( mod x^{2n}
ight)\
&equiv f_{0}left( 1-ln f_{0}+A
ight) left( mod x^{2n}
ight)
end{aligned})
至此，我们推完了，拿出来，写在下面
(fequiv f_{0}left( 1-ln f_{0}+A ight) left( mod x^{2n} ight))
还是倍增
求(ln)和多项式乘法都是(O(nlogn))的，加法是(O(n))的
时间复杂度(O(nlogn))
多项式开方
求(f=sqrt {A}) ((A)的常数项存在平方根)的前(n)项
构造(g(f)=f^2-A)
我们知道(f)的常数项为(A)常数项的平方根
可用二次剩余方法解
对(g)求导(g'(f_0)=2f_0)
根据牛顿迭代
(fequiv f_{0}-dfrac {f^{2}_{0}-A}{2f_{0}}left( mod x^{2n}
ight))
时间复杂度(O(nlogn))
如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧
如能得到推荐博主就更开心了
您的鼓励是博主的动力