分类 算法 下的文章

ZJOI 2019 了,机房同学也差不多都会基本多项式了,就写篇有关简单的多项式操作复习笔记吧 QAQ

约定:以下操作默认 n = \deg(F(x)) + 1 ,等号一般表示在 \bmod\ {x^n} 的意义下同余。

多项式乘法

可以先把多项式的系数转为点值,各位分别乘起来以后再插值出原多项式。考虑到单位根 / 原根的性质,我们有 FFT / NTT 。

READ MORE

写于:2019-01-13 20:44

更新于:2019-03-16 11:45

二项式反演:

\begin{aligned} f_n=\sum_{i=0}^{n}(-1)^i {n \choose i} g_i &\Leftrightarrow g_n=\sum_{i=0}^{n}(-1)^i {n \choose i} f_i \\ f_n=\sum_{i=0}^{n}{n \choose i} g_i &\Leftrightarrow g_n=\sum_{i=0}^{n}(-1)^{n-i} {n \choose i} f_i \end{aligned}

READ MORE

定义:给定两个 n 次多项式 F(x)G(x) ,若对于任意多项式 P(x) 都有 G(F(P)) = P 则称 G(x)F(x) 的复合逆在模 x^n 意义下的复合逆。可以证明,若两个多项式常数项为 0 且一次项不为 0 则复合逆唯一且满足 F(G(x)) = G(F(x)) = x

遗憾的是,多项式复合逆没有 o(n \log n) 的做法,但我们可以以 O(n \log n) 的复杂度求出某一项,或者 O(n^2) 的复杂度求出所有项。

拉格朗日反演即

[x^n]F(x) = \frac 1n [x^{-1}] \frac 1 {G^n(x)}

可以证明

[x^n]F(x) = \frac 1n [x^{n-1}] (\frac x {G(x)})^n

后者可以直接快速幂(两只 \log),或者转换为 \ln\exp ,可以参考 关于求多项式 k 次幂的一些思考

如果需要证明可以参考 zjt 大爷的博客 (我是不会)。

READ MORE