多项式求导
函数(f(x))的导函数(f^{'}(x))有如下性质：
((f(x)pm g(x))^{'}=f^{'}(x)pm g^{'}(x))
((f(x)g(x))^{'}=f^{'}(x)g(x)+f(x)g^{'}(x))
而且对于单项式(f(x)=x^n)，其导数(f^{'}(x)=nx^{n-1})，所以其(k(kleq n))阶导数(f^{(k)}(x)=frac{n!}{(n-k)!}x^{n-k})
相应的，对于多项式(f(x)=sum_{i=0}^na_ix^i)，其导数(f(x)=sum_{i=0}^{n-1}a_{i+1}(i+1)x^i)，其(k(kleq n))阶导数(f^{(k)}=sum_{i=0}^{n-k}a_{i+k}frac {(i+k)!}{i!}x^i)
(T(n)=O(n))
多项式积分
在一定程度上，积分是求导的逆运算
若(f(x)=sum_{i=0}^{n-1}a_ix_i)
即(int f^{'}(x)cdot dx=sum_{i=1}^{n}frac {a_{i-1}}{i}x^i)
(T(n)=O(n))
注意同一多项式求导需要逆序
多项式翻转
NOIP考点，但有个式子可以留意：(f^{R}(x)=x^nf(frac 1x))
多项式求逆
单个元素的逆元应该是是会求的，比如说一个数(t)的逆元在膜质数意义下为(t^{p-2})
但现在要求求一个多项式的逆元，联想到在模数为(x)时可以快速求得其逆元为(a(0)^{-1})，可以考虑从这里开始递推
对于题目可设
(a*bequiv 1pmod {x^{2p}}\a*cequiv 1pmod {x^p})
即已知(a,c)求(b)
(a*bequiv 1pmod {x^p}\a*cequiv 1pmod {x^p})
(Rightarrow b-cequiv 0pmod {x^p})
(Rightarrow b^2-2bc+c^2equiv 0 pmod {x^{2p}})
同乘(a)
(Leftrightarrow ab^2-2abc+ac^2equiv 0 pmod {x^{2p}})
考虑到(abequiv 1pmod {x^{2p}})
(Leftrightarrow b-2c+ac^2equiv 0 pmod {x^{2p}})
(Leftrightarrow bequiv 2c-ac^2 pmod {x^{2p}})
(T(n)=O(nlog_2 n))
牛顿迭代法
①
可以用来比较高效地求解多项式函数(f(x)=sum_{i=0}^na_ix^i)零点的近似解，大致过程是，选取(x_0)作为零点的近似值（当然这个近似值很可能差距很大，但经过若干次牛顿迭代后将会接近零点），然后求过点((x_o,f(x_0)))关于(f(x))的切线(l),然后得到直线(l)的零点(x_1)作为新的近似值，如此反复，得到的(x_i)会收敛
②
求解使得(F(f(x))=0pmod {x^n})的多项式(f(x))
可以用类似多项式求逆的方法，从(mod x^1)的情况下开始推导至(mod x^n)的情况，(mod x^1)的情况可以直接求得，设当前(F(f_0(x))equiv 0pmod {x^{lceil frac k2 ceil}})，现在要求解(F(f(x))equiv 0pmod {x^k})，在(f_0(x))处展开(F(f(x)))：
由于(f(x))与(f_0(x))中前(lceil frac k2 ceil)项是相同的，所以多项式((f(x)-f_0(x))^t)当(tgeq 2)时在(mod x^k)情况下为(0)，所以
由于(F(f(x))equiv 0pmod {x^k})，所以可推得
这个式子貌似很有用
多项式开根
已知(g(x))，求解(f(x)^2equiv g(x)pmod {x^n})
(f(x)^2-g(x)equiv 0pmod {x^n})
则有(F(f(x))equiv f_0(x)^2-g(x)pmod {x^n}\F^{'}(f(x))equiv 2f_0(x)pmod {x^n})
由上述牛顿迭代得到的式子可知
(f(x)equiv f_0(x)-frac{F(f_0(x))}{F^{'}(f_0(x))}pmod {x^n})
(f(x)equiv f_0(x)-frac {f_0(x)^2-g(x)}{2f_0(x)}pmod {x^n})
(f(x)equiv frac {f_0(x)^2+g(x)}{2f_0(x)}pmod {x^n})
(T(n)=O(nlog_2n))
另外常数项如果非1则需要求二次剩余，然而我并不会
多项式求ln
已知(f(x))，求解(ln(f(x)))
((ln f(x))^{'}=frac {d ln f(x)}{d~f(x)}cdot frac{d~f(x)}{dx}=(ln f(x))^{'}cdot f^{'}(x)=frac{f^{'}(x)}{f(x)})
所以
(ln f(x)=large int small(ln f(x))^{'}=large int small frac {f^{'}(x)}{f(x)})
(T(n)=O(nlog_2n))
多项式求exp
已知(g(x))，求解(f(x)=e^{g(x)})
令(F(f(x))=ln f(x)-g(x)equiv 0pmod {x^n})
则有(F^{'}(f(x))equiv frac 1{f(x)})
由上述牛顿迭代得到的式子可知
(f(x)equiv f_0(x)-frac{F(f_0(x))}{F^{'}(f_0(x))}pmod {x^n})
(f(x)equiv f_0(x)-frac {ln f_0(x)-g(x)}{frac 1{f_0(x)}}pmod {x^n})
(f(x)equiv f_0(x)(1-ln f_0(x)+g(x))pmod {x^n})
(T(n)=O(nlog_2n))
多项式求k次方
暴力(O(nlog_2nlog_2k))
但数学就是那么神奇，转个弯可以加速
(f(x)^k=(e^{ln f(x)})^k=e^{kcdot ln f(x)})
(T(n)=O(nlog_2n))
多项式除法&取模
已知(n)次多项式(A(x))和(m)次多项式(B(x))，求解(n-m)次多项式(f(x))与(k(k<m))次多项式(g(x))，使得(A(x)=f(x)B(x)+g(x))
消除(g(x))的影响，将(f(x))翻转
(x^nA(frac 1x)=x^nf(frac 1x)B(frac 1x)+x^ng(frac 1x))
(Leftrightarrow x^nA(frac 1x)=x^{n-m}f(frac 1x)x^mB(frac 1x)+x^{n-m+1}x^{m-1}g(frac 1x))
(Leftrightarrow A^R(x)=f^R(x)B^R(x)+x^{n-m+1}g^R(x))
这个式子在模(x^{n-m+1})的情况下，关于(g^R(x))的项恒为零，同时(deg~f^R(x)<n-m+1)不受影响，就可以得到(f^R(x))的真实值(f^R(x)=frac {A^R(x)}{B^R(x)}mod {x^{n-m+1}})，对(f^R(x))翻转可得(f(x))，同时计算出(g(x)=A(x)-f(x)B(x))