n^2 ln exp

有一些题目模数不是 NTT 模数或者多项式的长度比较短，利用 NTT 的多项式板子反而会很慢，这时候就需要使用 (Theta(n^2)) 的多项式 ln 和 Exp。

记两个多项式 (A(x)) 和 (B(x)) , (A_i) 为 (A(x)) 的 (i) 次项系数 , (B_i) 为 (B(x)) 的 (i) 次项系数 , 满足 (A_0 = 1) (B_0 = 0)

(A(x) = e^{B(x)})

(B(x) = ln(A(x)))

两边求导：

(B'(x) = frac{A'(x)}{A(x)})

(xA(x)B'(x) = xA'(x))

(nA_n = sumlimits_{i=1}^{n} iB_iA_{n-i})

(A_n = frac{1}{n}sumlimits_{i=1}^{n} iB_iA_{n-i})

(B_n = A_n - frac{1}{n}sumlimits_{i=1}^{n-1} iB_iA_{n-i})

然后就可以 (Theta(n^2)) 求 ln 和 Exp 了。