简述
在计数题解题中遇到要求 \(x \bmod m = 0\) 的条件时，如果式子的计算复杂度比较高，但是式子里含有二项式系数的时候，就可以考虑用单位根反演。
分类： 数学
生成函数 | Generating Function
二项式反演
对称的反演
二项式反演的主要内容就是：
\[ 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 \]
反演基础
定义
如果我们知道\(\{ f_n \}, \{ g_n \}\)有这种情况时：
\[ f_n = \sum_{i = 0}^n a_{ni} g_i \]
那么我们就可以用已知的\(f_0, f_1, \dots, f_n\)的值来求出\(g_n\)：
\[ g_n = \sum_{i = 0}^n b_{ni} f_i \]
上面这种求值方式叫做反演。
泰勒展开
定义
对于一个函数\(f(x)\)，如果该函数在其定义域上处处可导，则可以写成一个多项式函数（也就是这个函数的泰勒展开）。一般的，我们有：
\[ f(x) = \sum_{n = 0}^{\infty} \frac{f^{(n)}(x_0)}{n!}(x – x_0)^n \]
当\(x_0 = 0\)时，这个式子亦成为麦克劳林级数。
多项式求逆
前置技能
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)\)：