几个结论
Soulist
·
·
个人记录
今晚问贺知临一些问题，终于搞懂了一些之前不知道的芝士。
就假设$f'(x)$表示对$f(x)$求导$...
f(x)=x^2
f'(x)=2x
然后有一个结论：
求导和做积分是互逆的计算
比如f求导是g
那么g做积分是f
比如
f(x)=x^2->f'(x)=2x
f(x)=2x->g(x)=x^2
貌似有一个结论：
f(x)=x^a->f(x)=a*x^{a-1}
然后积分因为是面积所以可以逐项加起来
于是对多项式求积分就只需要对每一项求积分然后加起来即可
e.g:
然后还有一个结论（反向）：
f(x)=x^k->g(x)=\dfrac{1}{k+1}*x^{k+1}
于是就可以逐项加起来
然后还有一个结论是系数可以直接乘上去
这个东西的理由也一样，乘法看作多次加法，积分是可加的...
于是：
k*x^a=\dfrac{k}{a+1}x^{a+1}
也有：
k*x^a=k*ax^{a-1}
然后求导运算有一些规律：
e.g:
1.(f(x)*g(x))'=f'(x)*g(x)+f(x)*g'(x)
证明：
(f*g)'(x)=\dfrac{(f*g)(x+dx)-(f*g)(x)}{dx}
\dfrac{(f*g)(x+dx)-f(x+dx)g(x)+f(x+dx)g(x)-(f*g)(x)}{dx}
\dfrac{f(x+dx)(g(x+dx)-g(x))+g(x)*(f(x+dx)-f(x))}{dx}
于是就有：
因为\lim_{dx\to 0}f(x+dx)=f(x)
所以就有：
原式=
f(x)*g'(x)+g(x)*f'(x)
于是：
(f*g)(x)=f(x)*g'(x)+g(x)*f'(x)
2.f(g(x))'=f'(g(x))*g'(x)
证明：
f(g(x))'=\dfrac{f(g(x+dx))-f(g(x))}{dx}
可以构造dg=\dfrac{}{dx}
(\dfrac{f(x)}{g(x)})'=\dfrac{f'(x)g(x)-g'(x)f(x)}{g(x)^2}
然后结论：
ln'(x)=\dfrac{1}{x}
然后接下来推一下多项式\rm ln
B(x)=ln(A(x))
两边同时求导得：
令u=A(x)
B'(x)=ln'(u)*A'(x)
又ln'(u)=\dfrac{1}{u}
所以得：
B'(x)=\dfrac{A'(x)}{A(x)}
所以就只需要计算出A'(x)即可
因为求导与积分互逆，所以求导可加=积分可加，个人感觉
首先有对一个数求导是0
所以我们知道
A'(x)=\sum_{i=1}^na_i*ix^{i-1}
然后在求一下A(x)的逆A^{-1}(x)
然后将A'(x)和A^{-1}(x)乘起来就好了qwq
然后还原回去就套用上面的公式
顺便回忆一下多项式求逆吧...（雾
A'(x),A(x),B(x)
A'(x)*A(x)=1(mod~x^n)
B(x)*A(x)=1(mod~x^{n/2})
于是：
(A'(x)-B(x))*A(x)=0(mod~x^{n/2})
显然是因为左边变成了0
所以：
A'(x)-B(x)=0(mod ~x^{n/2})
(A'(x)-B(x))^2=0(mod~x^n)
A'(x)^2+B(x)^2-2A'(x)B(x)=0(mod~~x^n)
同时乘A得：
A'(x)+B(x)^2*A(x)-2B(x)=0(mod~x^n)
于是：
A'(x)=2B-B^2*A
递归处理即可
复杂度为T(x)=x\log x+T(x/2)
即O(n\log n)
好乱...以后补充到多项式全家桶里面去了qwq
2.$多项式$\rm exp
泰勒展开
首先是一个函数的泰勒展开：
F(x)=f(x_0)+\sum_{i=1}^{\infty}\dfrac{f^{i}(x_0)(x-x_0)^i}{i!}
其中f^i表示i阶导数
然而在精度允许的条件下由于阶乘非常的大所以只需要把n开到12,13左右即可
然后由于我们可以随便选择一个x_0进行泰勒展开，所以一般选择0
于是我们就可以将原式转化为
F(x)=f(0)+\sum_{i=1}^{\infty}\dfrac{f^i(0)*x^i}{i!}
牛顿迭代
用于求解0点
与二分不同的是牛顿迭代的求法是对一个函数求导，降次，求解降次后的0点以逼近原函数的0点
多项式牛顿迭代即求解满足G(F(x))=0(mod~~x^n)的解F(x)
n=1$的时候满足条件的多项式可以直接求出来，这个时候只有常数项，令常数项$=0
假设现在已经求出了：
G(F_0(x))=0(mod ~~x^{n/2})
考虑拓展到x^n次意义下，可以在G(F_0(x))处将G(F(x))泰勒展开变成：
G(F(x))=G(F_0(x))+\sum_{i=1}^n\dfrac{G^{i}(F_0(x))*(F(x)-F_0(x))^i}{i!}
因为我们有：G(F(x))=0(mod~~x^n)
所以就有：
G(F(x))=G(F_0(x))+\sum_{i=1}^n\dfrac{G^{i}(F_0(x))*(F(x)-F_0(x))^i}{i!}=0(mod~~x^n)
又G(F_0(x))=0(mod~~x^{n/2})
然后又由于理论上应该有：F(x)和F_0(x)的n/2项应该相等
所以那个奇怪的减法会导致这个函数没有最后n/2项
于是就发生了神奇的结论！
F(x)-F_0(x)
没有最后n/2项
所以(F(x)-F_0(x))^2没有最后n-1项
于是令人惊喜的是我们泰勒展开的第二项就是(F(x)-F_0(x))^2
所以我们居然只需要展开两项即可！！！woc
所以就得到了神奇的结论：
G(F(x))=G(F_0(x))+G'(F_0(x))*(F(x)-F_0(x))=0(mod~~x^n)
于是就有：
F(x)=F_0(x)-\dfrac{G(F_0(x))}{G'(F_0(x))}(mod~~x^n)
于是就可以倍增处理了...
问题的关键主要是对G'(F_0(x))求导才对吧...
下面给出两个对于G'(F_0(x))求导的例子：
多项式\exp
现在想要求解：
B(x)=e^{A(x)}
于是两边同时取\ln得：
\ln B(x)-A(x)=0
可以设G(B(x))=\ln B(x)-A(x)于是问题变成求解它的0点
这个多项式里面A(x)为定值，而B(x)为变量
我们假设有：
G(H(x))=0(mod~~x^{n/2})
问题是求解B(x)
于是代入牛顿迭代的公式得到：
B(x)=H(x)-\dfrac{G(H(x))}{G'(H(x))}
因为G'(H(x))=\ln H(x)-A(x)
而其中A(x)为常量，由于求导的可加性，A'(x)=0，简单求和可以得到：
G'(H(x))=\dfrac{1}{H(x)}
所以我们可以得到：
B(x)=H(x)-(\ln H(x)-A(x))*H(x)
B(x)=H(x)(1-\ln H(x)+A(x))
然而因为求解\ln H(x)的复杂度是O(n\log n)的
于是求解\exp的复杂度也是T(x)=x\log x+T(x/2)
即O(n\log n)
不过常数比较大就是了......
多项式开根
与上面类似
假设有
B(x)=\sqrt {A(x)}\quad (mod~~x^n)
两边同时平方得到：
B^2(x)-A(x)=0\quad (mod~~x^n)
可以设一个函数G(B(x))=B^2(x)-A(x)
代入牛顿迭代的式子就是：
B(x)=H(x)-\dfrac{G(H(x))}{G'(H(x))}
然后类似的，将A(x)看作常量，那么可以得到：G'(B(x))=2B(x)
所以得到：
B(x)=H(x)-\dfrac{H(x)^2-A(x)}{2H(x)}
B(x)=\dfrac{1}{2}H(x)+\dfrac{A(x)}{2H(x)}
于是要求逆，复杂度O(n\log n)
常数也比较大qwq