算法核心
二项式反演与莫比乌斯反演类似，都可以用于在给定的条件式实现两个函数之间的相互推算。二项式反演适用于，其核心反演式子有二：
- \[f(n) = \sum_{i=0}^n (-1) ^ iC_n^i g(i) \iff g(n) = \sum_{i=0}^n (-1)^i C_n^if(i) \]
- \[f(k) = \sum_{i = k} ^ nC_i^k g(i) \iff g(k) = \sum_{i=k}^n(-1)^{i-k}C_i^kf(i) \]
\((1)\) 式类似于容斥原理的一个小变形，这一式也非常符合我们对容斥的认识。事实上，这也不难用原集和补集之间的转化来证明。
\((2)\) 式看起来就相当的奇怪了。我们先来尝试证明它的正确性。我们将等式右边带入等式左边：
\[f(k) = \sum_{i = k}^n C_i^k g(i) \]\[f(k)= \sum_{i=k}^n C_i^k \sum_{j=i}^n (-1)^{j-i}C_j^if(j) \]\[f(k) = \] 标签：sum,对容斥,反演,iff,等式,二项式 From： https://www.cnblogs.com/little-corn/p/18172546