二项式反演

对称的反演

二项式反演的主要内容就是:

\[ f_n = \sum_{i = 0}^n (-1)^i {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^i {n \choose i} f_i \]

这个反演的式子非常的优美:在这种形式下,它们是对称的。当然,亦可以写作:

\[ f_n = \sum_{i = 0}^n {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^{n – i} {n \choose i} f_i \]

继续阅读二项式反演

多项式求逆

前置技能

FFT、NTT、多项式乘法。

原理推理

现在我们有一个这样的式子:

\[ A(x)B(x) \equiv C(x) \ (mod \ x^n) \]

现在我们已知\(B(x), C(x)\)的信息,而我们计算答案的时候需要用\(A(x)\)进行运算。这个时候,我们需要求出\(B(x)\)的逆元。多项式求逆元,我们一般是用倍增的方式来求解。假如我们有\(B(x)\)在模\(x^{\lceil \frac{x}{2} \rceil}\)意义下的逆元\(D(x)\):

继续阅读多项式求逆

多项式乘法 & 快速傅立叶变换

简述

在信息学竞赛中,多项式乘法出现得非常的多,朴素算法的时间复杂度为\(O(n^2)\),成为了许多毒瘤出题人卡指数的地方。所以,用快速傅立叶变换(FFT, Fast Fourier Transform)来优化多项式乘法是很有必要的。接下来,我会由浅入深地来介绍这两者与其之间的关系。

继续阅读多项式乘法 & 快速傅立叶变换