多项式算法

多项式算法

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

约定

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

多项式乘法

应用

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

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

多项式求乘法逆

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

可以用定义法配合分治 FFT 在 $O(n{\log }^{2}n)$ 的时间内解决： $$\begin{array}{}\text{(1)}& h_n={\displaystyle \frac{-\sum _{i\in [0,n)}{f}_i{h}_{n-i}{x}^n}{f_n{x}^n}}\end{array}$$

第二种方式是倍增法，假设我们已经求出了 $H^{\prime }(x)$ 满足 $H^{\prime }(x)\ast F(x)\equiv 1(\mathrm{mod}{x}^{\lceil \frac{n}{2}\rceil })$。又显然有 $H(x)\ast F(x)\equiv 1(\mathrm{mod}{x}^{\lceil \frac{n}{2}\rceil })$。两式相减得 $(H^{\prime }(x)-H(x))\ast F(x)\equiv 0(\mathrm{mod}{x}^{\lceil \frac{n}{2}\rceil })$。平方得 $(H^{\prime }(x)-H(x){)}^2\ast F^2(x)\equiv 0(\mathrm{mod}{x}^n)$。 $$\begin{array}{}\text{(2)}& (H^{\prime }(x)-H(x){)}^2\ast F^2(x)& \equiv 0(\mathrm{mod}{x}^n)\text{(3)}& H^{\prime 2}(x)F^2(x)-2H^{\prime }(x)H(x)F^2(x)+H^2(x)F^2(x)& \equiv 0(\mathrm{mod}{x}^n)\text{(4)}& H^{\prime 2}(x)F(x)-2H^{\prime }(x)+H(x)& \equiv 0(\mathrm{mod}{x}^n)\text{(5)}& H(x)& \equiv -2H^{\prime }(x)-H^{\prime 2}(x)F(x)(\mathrm{mod}{x}^n)\end{array}$$ 其中第二行到第三行先同时除以 $F(x)$ 再对 $F(x)$ 和 $H(x)$ 进行乘法得到 $1$。

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