多项式算法

多项式算法

多项式是组合计数题目中非常重要的工具。

约定

幂级数用大写字母表示，系数用对应的小写字母表示，对于 $F(x)$，$f_i$ 就是 $F(x)[x^i]$。

多项式乘法

应用

对于形如 $f_k=w(k)\sum\limits_{i+j=k}a_ib_j$ 的 $f_k$，可以利用多项式乘法在 $O(n\log n)$ 的时间里解决。

或者说，对于形如 $F(x)=A(x)\cdot(B(x) * C(x))$ 的幂级数 $F(x)$ ，可以在 $O(n\log n)$ 的时间里求出。

多项式求乘法逆

一般被描述对于一个 $F(x)$ 找一个 $H(x)$，满足 $F(x) * G(x)\equiv 1\pmod{x^n}$。

可以用定义法配合分治 FFT 在 $O(n\log^2 n)$ 的时间内解决：

$$h_n=\dfrac{-\sum\limits_{i\in[0,n)}f_ih_{n-i}x^n}{f_nx^n}$$

第二种方式是倍增法，假设我们已经求出了 $H’(x)$ 满足 $H’(x) F(x)\equiv 1\pmod{x^{\lceil\frac{n}{2}\rceil}}$。又显然有 $H(x) F(x)\equiv 1\pmod{x^{\lceil\frac{n}{2}\rceil}}$。两式相减得 $(H’(x) - H(x)) F(x)\equiv 0\pmod{x^{\lceil\frac{n}{2}\rceil}}$。平方得 $(H’(x) - H(x))^2 F^2(x)\equiv 0\pmod{x^n}$。

$$\begin{align} (H'(x) - H(x))^2 * F^2(x)&\equiv 0\pmod{x^n}\\ H'^2(x)F^2(x)-2H'(x)H(x)F^2(x)+H^2(x)F^2(x)&\equiv 0\pmod{x^n}\\ H'^2(x)F(x)-2H'(x)+H(x)&\equiv 0\pmod{x^n}\\ H(x)&\equiv -2H'(x) - H'^2(x)F(x)\pmod{x^n}\\ \end{align}$$

其中第二行到第三行先同时除以 $F(x)$ 再对 $F(x)$ 和 $H(x)$ 进行乘法得到 $1$。

对于 $n=1$ 我们显然有 $H’(x)=f_0^{-1}$，然后依次推出即可。