标签：数学公式 sum 速记 反演 brack binom bmod 式子

一、 反演与容斥

a) 综述：

1. 定义：反演就是序列函数的互反关系，即转移矩阵互逆。
2. 作用：将“恰好”之类的严格，放宽成更简洁的条件，方便统计。
3. 另一种理解：求出一个不是那么正确的答案，用反演来修正式子。
4. 分类：二项式反演、斯特林反演、莫比乌斯反演、欧拉反演、Min-max 反演、集合反演等等，下面分别介绍。

b) 二项式反演：

1. 形式：

\[f(k)=\sum_{i\in[0,k]}\binom kig(i)\Rightarrow g(k)=\sum_{i\in[0,k]}(-1)^{k-i}\binom kif(i) \]

\[f(k)=\sum_{i\in[k,+\infty)}\binom ikg(i)\Rightarrow g(k)=\sum_{i\in[k,+\infty)}(-1)^{i-k}\binom ikf(i) \]

1. 使用：题目中若是出现“恰好”k 个满足条件，就可以反演成“指定”k 个满足条件，方便计数；但是实际中可能会出现没想到反演的情况。

利用（差）卷积加速二项式反演：将式子化成如下形式，就可以是 O(nlogn)。

标签：数学公式,sum,速记,反演,brack,binom,bmod,式子
From： https://www.cnblogs.com/Zaunese/p/18046435