多項式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，是以常數巨大。