二项式反演学习笔记
Warriors_Cat
2020-12-01 16:05:25
~~诶不是我 NOIp 前为什么要开这个坑（~~
对这个东西刚入门，有错轻喷。
sto 反演带师 [MCAdam](https://www.luogu.com.cn/user/81238) orz
## 0. 前置知识
### 二项式定理：
$$(a+b)^n=\sum_{i=0}^n\binom{n}{i}a^ib^{n-i}$$
常见形式：
$$(x+1)^n=\sum_{i=0}^n\binom{n}{i}x^i$$
$$(x-1)^n=\sum_{i=0}^n(-1)^i\binom{n}{i}x^i$$
$$0=(1-1)^n=\sum_{i=0}^n(-1)^i\binom{n}{i}$$
### 组合恒等式
$$\binom{n}{i}\binom{i}{j}=\binom{n}{j}\binom{n - j}{i - j}$$
* 证明 $1:$
$$\begin{aligned}\mathrm{LHS}&=\dfrac{n!}{(n-i)!\cdot i!}\cdot\dfrac{i!}{(i-j)!\cdot j!}\\&=\dfrac{n!}{(n-j)!\cdot j!}\cdot\dfrac{(n-j)!}{[(n-j)-(i-j)]!\cdot(i-j)!}\\&=\binom{n}{j}\binom{n-j}{n-i}\end{aligned}$$
$$\mathcal{Q.E.D}$$
* 证明 $2:$
考虑组合意义。
左式相当于从 $n$ 只猫中选 $i$ 只猫，再从这 $i$ 只猫中选 $j$ 只猫的方案数。
那么我们可以转化为从 $n$ 只猫中选 $j$ 只猫，再从剩下的 $n-j$ 只猫中选 $i-j$ 只猫来使得包含关系仍然成立。
于是就有原式。
$$\mathcal{Q.E.D}$$
这两个式子**很重要！！很重要！！很重要！！**
## 1. 基本公式
二项式反演最核心的一条公式：
$$f(n) = \sum_{i=0}^n(-1)^i\binom{n}{i}g(i) \iff g(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}f(i)$$
~~没错就是这么对称~~
* 证明：
考虑 $n$ 个集合 $A_1 - A_n$。
根据容斥原理可得
$$|A_1\cap A_2\cap...\cap A_n|=|S|+\sum_{i=1}^n(-1)^i \sum|\bar{A_{x_1}}\cap \bar{A_{x_2}}\cap...\cap \bar{A_{x_i}}|$$
$$|\bar{A_1}\cap \bar{A_2}\cap...\cap \bar{A_n}|=|S|+\sum_{i=1}^n(-1)^i \sum|A_{x_1}\cap A_{x_2}\cap...\cap A_{x_i}|$$
如果有
$$f(i)=|A_{x_1}\cap A_{x_2}\cap...\cap A_{x_i}|$$
$$g(i)=|\bar{A_{x_1}}\cap \bar{A_{x_2}}\cap...\cap \bar{A_{x_i}}|$$
那么就有
$$f(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}g(i)$$
$$g(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}f(i)$$
显然这两个有等价和相互推导的关系，于是：
$$f(n) = \sum_{i=0}^n(-1)^i\binom{n}{i}g(i) \iff g(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}f(i)$$
$$\mathcal{Q.E.D}$$
然而，尽管这个式子很对称，我们并不常用。
常用的是下面两个式子：
$$1.f(n)=\sum_{i=0}^n\binom{n}{i}h(i) \iff h(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)$$
* 证明：
令 $h(n) = (-1)^ng(n)$。
带回那个对称式：
$$f(n)=\sum_{i=0}^n(-1)^i\binom{n}{i}g(i)=\sum_{i=0}^n\binom{n}{i}h(i)$$
$$\dfrac{h(n)}{(-1)^n}=\sum_{i=0}^n(-1)^i\binom{n}{i}f(i) \iff h(n)=\sum_{i=0}^n(-1)^{i+n}\binom{n}{i}f(i)$$
由于 $n+i$ 与 $n-i$ 奇偶性相同，于是
$$f(n)=\sum_{i=0}^n\binom{n}{i}h(i) \iff h(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)$$
$$\mathcal{Q.E.D}$$
另外，这个式子还可以改写成：
$$f(n)=\sum_{i=m}^n\binom{n}{i}h(i) \iff h(n)=\sum_{i=m}^n(-1)^{n-i}\binom{n}{i}f(i)$$
证明的话……用用前缀和思想就行了？
$$2.f(n)=\sum_{i=n}^m\binom{i}{n}h(i) \iff h(n)=\sum_{i=n}^m(-1)^{i-n}\binom{i}{n}f(i)$$
证明同理，这里就不赘述了。
## 2.常见用法
那，这个鬼东西到底有什么用呢？
比如说，我们观察这个式子：
$$f(n)=\sum_{i=n}^m\binom{i}{n}g(i)$$
如果我们定义 $f(n)$ 为 **钦定** $n$ 个的方案数，$g(n)$ 为 **恰好** $n$ 个的方案数。（这里 **钦定** 可以认为是固定 $n$ 个，剩下的随意。）
那么上面这个式子显然成立。
我们可以看出 $f(n)$ 的限制比 $g(n)$ 宽松，于是我们可以先通过一些手段来求出 $f(n)$，然后再来用反演求 $g(n)$。
当然有的时候反演完还要推一堆乱七八糟的式子，这个考验数学功底了。
还有，看见 **恰好，至少，至多** 这些字眼的计数题，可以考虑是不是容斥。
## 3.具体题目
[P4859 已经没有什么好害怕的了](https://www.luogu.com.cn/problem/P4859)
### $Description:$
给定 $n, k$ 和长度为 $n$ 的序列 $a_i, b_i$。将 $a_i, b_i$ 两两配对，使得 $a_i > b_i$ 的个数比 $b_i > a_i$ 的个数多 $k$，求有多少种配对方案。
### $Solution:$
易得 $a_i > b_i$ 的个数**恰好**为 $\dfrac{n+k}{2}$。
发现直接这样搞挺难的，于是想到容斥。
定义 $f(x)$ 为**钦定** $a_i > b_i$ 的个数为 $x$，$g(x)$ 为**恰好** $a_i > b_i$ 的个数为 $x$。
那么显然有
$$f(x)=\sum_{i=x}^n\binom{i}{x}g(i)$$
二项式反演一下，可得
$$g(x)=\sum_{i=x}^n(-1)^{i-x}\binom{i}{x}f(i)$$
我们要的就是 $g(\dfrac{n+k}{2})$。
于是只要求出 $f$ 函数就行了。
这里考虑 $\mathrm{DP}$。先对 $a, b$ 排个序，定义 $dp_{i, j}$ 为 $a_1$ 到 $a_i$ 中有 $j$ 对可配对的数。
那么就有状态转移方程：
$$dp_{i, j}=dp_{i-1,j}+dp_{i-1, j-1}\times (cnt_i-j+1)$$
其中 $cnt_i$ 为 $\sum_{j=1}^n[a_i > b_j]$。
然后 $f(x)=dp_{n, x}\times (n-x)!$。
完了。
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
#define ll long long
#define fi first
#define se second
#define y1 y_csyakioi_1
#define y0 y_csyakioi_0
#define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 2010, mod = 1000000009;
int n, k, a[N], b[N], fac[N], inv[N], f[N][N], F[N], G[N], cnt[N], tot, ans;
inline int fpow(int x, int p){ int ans = 1; for(; p; p >>= 1, x = 1ll * x * x % mod) if(p & 1) ans = 1ll * ans * x % mod; return ans; }
inline void initfac(int n){
fac[0] = 1;
for(int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
inv[n] = fpow(fac[n], mod - 2);
for(int i = n - 1; ~i; --i) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}
inline int C(int n, int m){ return n < m ? 0 : 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod; }
inline int pown1(int x){ return x & 1 ? mod - 1 : 1; }
int main(){
n = read(); k = read(); initfac(n);
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= n; ++i) b[i] = read();
if(n + k & 1) return puts("0") & 0; k = n + k >> 1;
sort(a + 1, a + n + 1); sort(b + 1, b + n + 1);
for(int i = 1; i <= n; ++i){
while(tot < n && b[tot + 1] < a[i]) ++tot;
cnt[i] = tot;
}
f[0][0] = 1;
for(int i = 1; i <= n; ++i){
f[i][0] = f[i - 1][0];
for(int j = 1; j <= i; ++j){
f[i][j] = (f[i - 1][j] + 1ll * f[i - 1][j - 1] * (cnt[i] - j + 1) % mod) % mod;
}
}
for(int i = 0; i <= n; ++i) F[i] = 1ll * f[n][i] * fac[n - i] % mod;
for(int i = k; i <= n; ++i){
ans = (ans + 1ll * pown1(i - k) * C(i, k) % mod * F[i] % mod) % mod;
}
printf("%d", ans);
return 0;
}
```
---
$To\ be\ continued......$