单位根反演

简述

在计数题解题中遇到要求 \(x \bmod m = 0\) 的条件时,如果式子的计算复杂度比较高,但是式子里含有二项式系数的时候,就可以考虑用单位根反演。

继续阅读“单位根反演”

二项式反演

对称的反演

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

\[ 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 \]

继续阅读“二项式反演”