题解 P4238 【【模板】多项式求逆】

· · 题解

多项式求逆

对于f，若有g，使得f\times g(x) = 1，称g为f的逆

给f，求g的前n项，即求\frac{1}{f(x)}的麦克劳林级数的前n项系数

例：f(x) = 1 - x

g(x) = \frac{1}{1 - x} = \sum_{i = 0}^{\infty} x^i 考虑倍增，设$g_t$的前$2^t$位与$g$相同，其余位为$0$，显然有$(f\times g)(x) \equiv 0 \pmod {2^{t+1}}

显然g_{(t+1)}(x) - g_t(x)的前2^t项为0，则(g_{t+1}(x) - g_t(x))^2的前2^{t+1}项为0，可得

(g_{t+1}^2-2g_{t+1}g_{t}+g_t^2)(x)\equiv 0 \pmod {2^{t+1}}

左乘f(x)，由(f\times g_{t+1})(x)\equiv 1 \pmod {2^{t+1}}

得到(g_{t+1}-2g_t+f\times g_t^2)(x) \equiv 0 \pmod {2^{t+1}}

g_{t+1} = 2g_t - f \times g_t^2 g_0 = a_0^{-1} T(n) = T(\frac{n}{2}) + O(n \log n = O(n \log^2 n)

代码就不贴了，板子都是一样的，大家可以去模litble的代码