二项式反演

对称的反演

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

\[ 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)\):

继续阅读多项式求逆