多项式exp-ln学习小结

前言

• 其实多项式exp/ln好像考的频率不算很高
• 不过总得来说只要多做生成函数计数题的话，多多少少还是会遇到的。

l n ( x ) ln(x) ln(x)的展开式

• 通过泰勒展开，可以得到：

  − l n ( x ) = x 1 + x 2 2 + x 3 3 + . . . -ln(x)=\frac{x}{1}+\frac{x^2}{2}+\frac{x^3}{3}+... −ln(x)=1x​+2x2​+3x3​+...

l n ( x ) ln(x) ln(x)的导数

• l n ( x ) ln(x) ln(x)有一个特殊的性质，就是如果 f ( x ) = l n ( x ) f(x)=ln(x) f(x)=ln(x)，则 f ′ ( x ) = 1 x f'(x)=\frac{1}{x} f′(x)=x1​。
• 那么对于一个多项式 A A A，我们可以考虑先求出 B = A − 1 B=A^{-1} B=A−1，然后把 B B B积分回去，就可以得到 l n ( A ) ln(A) ln(A)了。

e x e^x ex的展开式

• 通过泰勒展开，可以得到：

  e x = 1 + x 1 ! + x 2 2 ! + x 3 3 ! + . . . e^x=1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+... ex=1+1!x​+2!x2​+3!x3​+...

• 假如指数不是 x x x而是一个多项式的话，可以卷积多次来解决。
• 然而好像没有什么大用处。

牛顿迭代

• 对于一个多项式 A A A，假如我们已经求出了在 m o d    n 2 k − 1 \mod{n^{2^{k-1}}} modn2k−1下的答案 B 0 B_0 B0​，现在我们要推广到 m o d    n 2 k \mod{n^{2^k}} modn2k的答案 B B B。
• 看一看泰勒展开的式子： f ( x 1 ) = f ( x 0 ) + f ′ ( x 0 ) ∗ ( x 1 − x 0 ) 1 + f ′ ′ ( x 0 ) ∗ ( x 1 − x 0 ) 2 2 + . . . f(x1)=f(x0)+\frac{f'(x0)*(x1-x0)}{1}+\frac{f''(x0)*(x1-x0)^2}{2}+... f(x1)=f(x0)+1f′(x0)∗(x1−x0)​+2f′′(x0)∗(x1−x0)2​+...。
• 先假定函数 f ( x ) = l n ( x ) − A f(x)=ln(x)-A f(x)=ln(x)−A，其中 x x x可以是一个多项式。
• 则我们需要找到一个 x x x使得 f ( x ) = 0 f(x)=0 f(x)=0。
• 我们把 x 0 = B 0 , x 1 = B x0=B_0,x1=B x0=B0​,x1=B代入上述的泰勒展开。
• 则 x 1 − x 0 x1-x0 x1−x0的最低非零项至少在第 2 k − 1 2^{k-1} 2k−1项以后。
• 那么我们发现，对于 ( x 1 − x 0 ) p (x1-x0)^p (x1−x0)p，如果 p > = 2 p>=2 p>=2，那么它的最低非零项的次数大于 2 k 2^k 2k。
• 所以这个式子只有前两项 f ( x 0 ) + f ′ ( x 0 ) ∗ ( x 1 − x 0 ) f(x0)+f'(x0)*(x1-x0) f(x0)+f′(x0)∗(x1−x0)是有用的。
• 对于 f ( x ) = l n ( x ) − A f(x)=ln(x)-A f(x)=ln(x)−A，由于 f ′ ( x ) = 1 x f'(x)=\frac{1}{x} f′(x)=x1​，所以原式可以变成 f ( x 1 ) = f ( x 0 ) + x 1 − x 0 x 0 f(x1)=f(x0)+\frac{x1-x0}{x0} f(x1)=f(x0)+x0x1−x0​。
• 由于 f ( x 1 ) ≡ 0 ( m o d    n 2 k ) f(x1) \equiv 0(\mod n^{2^k}) f(x1)≡0(modn2k)，那么 f ( x 0 ) + x 1 − x 0 x 0 = 0 f(x0)+\frac{x1-x0}{x0}=0 f(x0)+x0x1−x0​=0。
• 可得 x 1 = x 0 − f ( x 0 ) ∗ x 0 = x 0 ∗ ( 1 − l n ( x 0 ) + A ) x1=x0-f(x0)*x0=x0*(1-ln(x0)+A) x1=x0−f(x0)∗x0=x0∗(1−ln(x0)+A)。
• 那么只需要求出 l n ( x 0 ) ln(x0) ln(x0)就可以得到 x 1 x1 x1了。
• 由于每一次ln的时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)的，则exp的时间复杂度为：
• T ( n ) = T ( n 2 ) + O ( n l o g n ) T(n)=T(\frac{n}{2})+O(nlogn) T(n)=T(2n​)+O(nlogn)
• 则 T ( n ) = O ( n l o g n ) T(n)=O(nlogn) T(n)=O(nlogn)，所以exp的时间复杂度是1个log的。
• 但要注意的是，虽然理论上是1个log的，但每次倍增要exp->ln->求逆，总共要9次DFT，所以常数巨大。