二项式反演
前置知识：二项式定理
对于 \(a\), \(b\)，显然有
\[(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k.
\]
二项式反演公式
设 \(f(n)\) 和 \(g(n)\) 是定义在非负整数集上的两个函数。如果对于所有非负整数 \(n\)，都有
\[g(n) = \sum_{k=0}^{n} \binom{n}{k} f(k),
\]
那么 \(f(n)\) 和 \(g(n)\) 之间存在如下关系：
\[f(n) = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} g(k).
\]
这个关系称为二项式反演公式。
证明
设函数 $ f(x) $，
设有算子 $ \Delta \(，\) 1 $ 是单位元，$ E $ 表示左移，其 \(n\) 次方表示进行 \(n\) 次计算，即：
\[\Delta = f(x+1) - f(x), \quad E = f(x+1)，1 = f(x)
\]
显然有：
\[\Delta = E - 1，E = \Delta + 1
\]
利用二项式定理展开，得：
\[E^n = (\Delta + 1)^n = \sum_{k=0}^{n} \binom{n}{k} \Delta^k
\]
\[\Delta^n = (E - 1)^n = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} E^k
\]
设 \(\Delta = f(x)\)，\(E = g(x)\)，则有：
\[g(n) = \sum_{k=0}^{n} \binom{n}{k} f(k),
\]
\[f(n) = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} g(k).
\]
对于计数题的应用
二项式反演对于解决“恰好”问题十分好做，可以将 “恰好” 转化为 “至少” 或者 “至多” 的问题，再通过二项式反演求解。
设总共有 \(N\) 个元素，\(f(n)\) 表示性质 \(A\) 恰好在 \(n\) 个元素中成立，\(g(n)\) 为 \(A\) 于至少 \(n\) 个元素中成立，而 \(h(n)\) 表示 \(A\) 在至多 \(n\) 个元素中成立，若对于 \(g(x)\) 和 \(h(x)\)都钦定至少或之多成立的为前 \(n\) 个，则有：
\[g(n) = \sum_{k = n}^{N} \binom{N}{k} f(k) \quad h(n) = \sum_{k = 0}^{n} \binom{N}{k} f(k)
\]
利用二项式反演公式，有：
\[f(n) = \sum_{k = n}^{N} (-1)^{k-n} \binom{k}{n} g(k)
\]
\[f(n) = \sum_{k = 0}^{n} (-1)^{n-k} \binom{n}{k} h(k)
\]
\(f(n)\) 与 \(h(n)\) 的转换为直接用公式，\(f(n)\) 与 \(g(n)\) 的转换需要变形后使用公式。（只取求和的后半阶段）
记忆技巧：求和的边界好记也很显然，后面算组合数和求 \(-1\) 的次幂时注意 \(k\) 与 \(n\) 的大小关系来决定位置，\(-1\) 的次幂是大减小，组合数是大的在上面。