多项式算法

多项式算法

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

约定

幂级数用大写字母表示，系数用对应的小写字母表示，对于 \(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}\)，然后依次推出即可。