多项式全家桶学习笔记

Fido_Puppy · 2022-12-14 11:02:29 · 个人记录

\texttt{Preface}

做多项式题就像嗑药，出多项式题就像贩毒。—— 某 FJ 知名 OI 选手

多项式乘法

给定 n - 1 次多项式 h(x)，求 h ^ {-1} (x)\pmod{x ^ n}。

题目可以转化成给定 h(x)，求一个多项式 f(x)，使得 g(f(x)) = f ^ {-1}(x) - h(x) = 0。

根据多项式牛顿迭代，假设已经求出 f_0(x) 表示 \pmod{x ^ {\lfloor \frac{n}{2} \rfloor}} 意义下的答案，现在要求 f(x) 表示 \pmod{x ^ n} 意义下的答案，则：

f(x) = f_0(x) - \dfrac{f_0 ^ {-1} (x) - h(x)}{-f_0^{-2}(x)}

f(x) = 2f_0(x) - f_0^2(x)\cdot h(x)

倍增即可，时间复杂度 T(n) = T(\dfrac{n}{2}) + \Theta(n \log n) = \Theta(n \log n)。

给定序列 g_{1 \cdots n - 1}，求序列 f_{0 \cdots n - 1}。

其中：

f_i = \sum_{j = 1}^i f_{i - j}\cdot g_{j}

并且 f_0 = 1。

首先提一下生成函数的做法。

设：

F(x) = \sum_{i = 0}^{\infty} f_i\cdot x ^ i, G(x) = \sum_{i = 1}^{\infty} g_i \cdot x ^ i

F(x) \cdot G(x) = F(x) - f_0

F(x) = \dfrac{f_0}{1 - G(x)} = {\left( 1 - G(x) \right)} ^ {-1}

然后多项式求逆，时间复杂度 \Theta(n \log n)。

给定多项式 F(x)，求多项式 G(x) = \ln F(x)。

G(x) = \ln F(x)

对于两边分别求导：

G'(x) = \dfrac{F'(x)}{F(x)}

G(x) = \int \dfrac{F'(x)}{F(x)}

然后多项式求逆，时间复杂度 \Theta(n \log n)。

考虑多项式牛顿迭代，给定多项式 h(x)，要求一个多项式 f(x)，使得 g(f(x)) = \ln f(x) - h(x) = 0。

f(x) = f_0(x) - \dfrac{\ln f_0(x) - h(x)}{{f_0(x)}^{-1}}

f(x) = f_0(x)\cdot\left(1 - \ln f_0(x) + h(x)\right)

时间复杂度 T(n) = T(\dfrac{n}{2}) + \Theta(n \log n) = \Theta(n \log n)。

\texttt{Thanks for watching!}